5.二叉树遍历

二叉树的数据结构

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

先序遍历

Leetcode 144. Binary Tree Preorder Traversal

//先序递归
class Solution {
public:
    
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==NULL) return vector<int>{};
        vector<int> res;
        preorderTree(root, res);
        return res;
    }
    void preorderTree(TreeNode* node, vector<int> &res){
        if(node==NULL) return;
        res.push_back(node->val);
        preorderTree(node->left, res);
        preorderTree(node->right, res);
    }
};

//先序非递归
class Solution {
public:
    
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==NULL) return vector<int>{};
        vector<int> res;
        stack<TreeNode*> st;
        st.push(root);
        TreeNode *node=NULL;
        while(!st.empty()){
            node = st.top();
            st.pop();
            res.push_back(node->val);
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return res;
    }
};

中序遍历

leetcode 94. Binary Tree Inorder Traversal

//中序递归
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorderTree(root, ans);
        return ans;
    }
    void inorderTree(TreeNode *node, vector<int> &ans){
        if(node==NULL) return;
        inorderTree(node->left, ans);
        ans.push_back(node->val);
        inorderTree(node->right, ans);
    }
};

//中序非递归
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==NULL) return vector<int>{};
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode *node=root;
        while(!st.empty() || node){
            if(node!=NULL){
                st.push(node);
                node=node->left;
            }else{
                node = st.top();
                st.pop();
                res.push_back(node->val);
                node=node->right;
            }
        }
        return res;
    }
};

后序遍历

  1. Binary Tree Postorder Traversal
//后序递归
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorderTree(root, res);
        return res;
    }
    void postorderTree(TreeNode* node, vector<int> &res){
        if(node==NULL) return;
        postorderTree(node->left, res);
        postorderTree(node->right, res);
        res.push_back(node->val);
    }
};

//后序非递归
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==NULL) return vector<int>{};
        vector<int> res;
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        st1.push(root);
        TreeNode *node = NULL;
        while(!st1.empty()){
            node = st1.top();
            st2.push(node);
            st1.pop();
            if(node->left) st1.push(node->left);
            if(node->right) st1.push(node->right);
        }
        while(!st2.empty()){
            node = st2.top();
            st2.pop();
            res.push_back(node->val);
        }
        return res;
    }
};

层序遍历

  1. Binary Tree Level Order Traversal
//层序遍历递归
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==NULL) return vector<vector<int>>();
        vector<vector<int>> ans;
        level(ans, root, 0);
        return ans;
    }
    void level(vector<vector<int>> &ans, TreeNode *root, int depth){
        if(ans.size()==depth) ans.push_back(vector<int>());
        ans[depth].push_back(root->val);
        if(root->left) level(ans, root->left, depth+1);
        if(root->right) level(ans, root->right, depth+1);
    }
};

//层序遍历非递归
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==NULL) return vector<vector<int>>();
        vector<vector<int>> ans;
        int idx=0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            TreeNode *node=NULL;
            ans.push_back(vector<int>());
            while(size--){
                node = q.front();
                q.pop();
                ans[idx].push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            idx++;
        }
        return ans;
    }
};

右视树

  1. Binary Tree Right Side View
//右视树递归实现
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(root==NULL) return vector<int>();
        vector<int> ans;
        recursion(root, 1, ans);
        return ans;
    }
    void recursion(TreeNode *root, int depth, vector<int> &ans){
        if(root==NULL) return;
        if(ans.size()<depth) ans.push_back(root->val);
        recursion(root->right, depth+1, ans);
        recursion(root->left, depth+1, ans);
    }
};

非递归的版本和层序遍历类似，只是将层序遍历循环中的vector变为stack即可，内循环结束，取top即可。

之字树

  1. Binary Tree Zigzag Level Order Traversal
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root==NULL) return vector<vector<int>>();
        vector<vector<int>> ans;
        queue<TreeNode *> q;
        q.push(root);
        bool Left2Right=true;
        while(!q.empty()){
            int size=q.size();
            vector<int> cur_vec(size);
            for(int i=0;i<size;i++){
                int idx = Left2Right?i:size-i-1;
                TreeNode * tmp = q.front();
                q.pop();
                cur_vec[idx] = tmp->val;
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            ans.push_back(cur_vec);
            Left2Right=!Left2Right;
        }
        return ans;
    }
};

查找离目标node的k距离的node

  1. All Nodes Distance K in Binary Tree
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
    unordered_map<TreeNode*, TreeNode*> backEdge;
    unordered_set<TreeNode*> visited;
    dfs(root, target, backEdge);
    queue<TreeNode *> q;
    q.push(target);
    vector<int> ans;
    while(!q.empty()){
        int size=q.size();
        for(int i=0;i<size;i++){
            TreeNode *tmp = q.front();
            visited.insert(tmp);
            q.pop();
            if(K==0) ans.push_back(tmp->val);
            if(!visited.count(backEdge[tmp])&&backEdge[tmp]) q.push(backEdge[tmp]);
            if(!visited.count(tmp->left)&&tmp->left) q.push(tmp->left);
            if(!visited.count(tmp->right)&&tmp->right) q.push(tmp->right);
        }
        K--;  
    }
    return ans;
}
void dfs(TreeNode *root, TreeNode *target, unordered_map<TreeNode*, TreeNode*> &backEdge){
    if(root==NULL || root==target) return;
    
    if(root->left){
        backEdge[root->left] = root;
        dfs(root->left, target, backEdge);
    }
    if(root->right){
        backEdge[root->right] = root;
        dfs(root->right, target, backEdge);
    }
}

根据中序和先序构建二叉树

  1. Construct Binary Tree from Preorder and Inorder Traversal
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return helper(0, 0, inorder.size()-1, preorder, inorder);
}
TreeNode *helper(int preStart, int inStart, int inEnd, vector<int>& preorder, vector<int>& inorder){
    if(preStart>preorder.size() || inStart>inEnd) return NULL;
    TreeNode *root = new TreeNode(preorder[preStart]);
    int idx=0;
    for(int i=inStart;i<=inEnd;i++){
        if(inorder[i]==root->val){
            idx=i;
            break;
        }
    }
    root->left = helper(preStart+1, inStart, idx-1, preorder, inorder);
    root->right = helper(preStart+idx-inStart+1, idx+1, inEnd, preorder, inorder);
    return root;
}

二叉树最大路径和

  1. Binary Tree Maximum Path Sum

int helper(TreeNode *node, int &ans){
    if(node==NULL) return 0;
    int left=max(helper(node->left, ans), 0);
    int right=max(helper(node->right, ans), 0);
    ans = max(ans, left+right+node->val);
    return max(left, right)+node->val;
    
}
int maxPathSum(TreeNode* root) {
    int ans=INT_MIN;
    helper(root, ans);
    return ans;
}

二叉树路径和

  1. Path Sum III
int pathSum(TreeNode* root, int sum) {
    if(root==NULL) return 0;
    return helper(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
int helper(TreeNode *node, int pre, int sum){
    if(node==NULL) return 0;
    int cur = pre + node->val;
    return (cur==sum) + helper(node->left, cur, sum) + helper(node->right, cur, sum);
}

一颗二叉树是否为另一颗二叉树的子树

  1. Subtree of Another Tree
bool isSubtree(TreeNode* s, TreeNode* t) {
    if(!s) return false;
    if(isSame(s, t)) return true;![](https://img2020.cnblogs.com/blog/917376/202009/917376-20200902201310016-1064326194.png)

   return isSubtree(s->left, t) || isSubtree(s->right, t);
}

bool isSame(TreeNode *node1, TreeNode *node2){
    if(!node1 && !node2) return true;
    if(!node1 || !node2) return false;
    if(node1->val != node2->val) return false;
    return isSame(node1->left, node2->left)&&isSame(node1->right,node2->right);
}

树的最大宽度

  1. Maximum Width of Binary Tree
int widthOfBinaryTree(TreeNode* root) {
   int ans;
   dfs(root, 0, ans, vector<int>()={});
   return ans;
}

void dfs(TreeNode* root, int level, int &ans, vector<int>& vec){
    if(root == NULL) return;
    if(vec.size() == level) vec.push_back(1);
    else vec[level]++;
    ans = max(ans, vec[level]);
    dfs(root->left, level+1, ans, vec);
    dfs(root->right, level+1, ans, vec);
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wangzi199/p/13409120.html