正文索引 [隐藏]

这次要记录的是做leetbook：二叉树的经历，这是一本很小的book，所以决定用一晚上的时间做完。传送门

树的遍历

t1 二叉树的先序遍历

常规操作，简单题要做难，所以考虑用多种方法来写。

递归法

最常规的递归法，按照根->左->右的顺序来写就可以了。

class Solution {
public:
    void solve(TreeNode*root, vector<int>& a) {
        if(root == NULL) return;

        a.push_back(root->val);
        solve(root->left, a);
        solve(root->right, a);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        solve(root, ans);
        return ans;
    }
};

迭代法

迭代法是用栈模拟递归的操作。因为栈具有先入后弹的特性，所以优先压右儿子进栈。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* tmp = st.top();st.pop();
            
            if(tmp != NULL) ans.push_back(tmp->val);
            else continue;
            
            st.push(tmp->right);
            st.push(tmp->left);
        }

        return ans;
    }
};

t2 二叉树的中序遍历

递归法

class Solution {
public:
    void solve(vector<int>& arr, TreeNode* node) {
        if(node == NULL) return;

        solve(arr, node->left);
        arr.push_back(node->val);
        solve(arr, node->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        solve(ans, root);
        return ans;    
    }
};

迭代法

中序遍历的迭代实现代码最为复杂。

先序遍历代码简洁的原因是它“遍历”与“处理”的操作同步进行。先序遍历的顺序是根左右，每次先访问根节点然后将其值压入答案数组，接着去访问左右子树。

但中序遍历并不是这样。中序遍历需要首先找到左子树的底部，然后开始按左根右的顺序访问节点。即在找到左子树底部之前的遍历操作中是不含有“压入答案”这个处理步骤的。

解决这个不同步问题的方法就是用一个指针去完成遍历的任务。当它找到了左子树的底部时，就开始操作。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* pointer = root;

        while(pointer != NULL || !st.empty())
        {
            //去遍历到左子树最底部
            if(pointer != NULL)
            {
                st.push(pointer);
                pointer = pointer->left;
            }
            //摸到最底部，开始操作
            else
            {
                pointer = st.top();st.pop();
                ans.push_back(pointer->val);
                pointer = pointer->right;
            }
        }

        return ans;
    }
};

t3 二叉树的后序遍历

递归法

class Solution {
public:

    void solve(vector<int>& arr, TreeNode* node) {
        if(node == NULL) return;

        solve(arr, node->left);
        solve(arr, node->right);
        arr.push_back(node->val);
    }
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        solve(ans, root);
        return ans;
    }
};

迭代法

后序遍历的迭代实现可以通过先序遍历的代码改进得到。

先序遍历的遍历顺序是根->左->右，后序遍历是左->右->根。那么首先调整先序遍历的代码，从 根->左->右改成根->右->左，然后在遍历完整棵树后翻转答案数组，这样就得到了按左->右->根顺序遍历的答案序列了。

 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        st.push(root);

        while(!st.empty())
        {
            TreeNode* tmp = st.top();st.pop();

            if(tmp != NULL) ans.push_back(tmp->val);
            else continue;

            st.push(tmp->left);
            st.push(tmp->right);
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

t4 二叉树的层序遍历

层序遍历顾名思义，一层一层的遍历。一般采用队列实现这个操作，每次对队首节点操作，将其左右子压入队，循环往复即可。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        que.push(root);

        if(root == NULL) return ans;

        while(!que.empty())
        {
            int size = que.size();
            vector<int> part;

            while(size--)
            {
                TreeNode* node = que.front();que.pop();
                part.push_back(node->val);

                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }

            ans.push_back(part);
        }

        return ans;
    }
};

运用递归解决问题

t1 二叉树的最大深度

要求二叉树的最大深度，那么就要自顶向下的找。

如果当前遍历到空节点，直接return；如果当前节点是叶子节点，那么维护ans为当前ans值与depth值之间的最大值，如果都不是，继续递归找左右子树，每次深度+1.

class Solution {
public:
    int ans = 0;

    void find(TreeNode* node, int depth) {
        if(node == NULL) return;

        if(node->left == NULL && node->right == NULL)
            ans = max(ans, depth);
        
        find(node->left, depth + 1);
        find(node->right, depth + 1);
    }

    int maxDepth(TreeNode* root) {
        find(root, 1);
        return ans;
    }
};

t2 对称二叉树

判断一颗二叉树是否是轴对称的，可以用两个指针，依然是自上而下的遍历，一个往左的时候另一个就往右，如果它们的值到叶子节点都一直相等，显然这棵树就是对称的。

class Solution {
public:

    bool check(TreeNode* l, TreeNode* r) {
        //同时走到叶子节点，显然对称
        if(l == NULL && r == NULL) return true;
        //不同时走到叶子节点，不对称
        if(l == NULL || r == NULL) return false;
        //如果当前两指针指向的节点值相等且它们的左右子树都满足相等，则本身对称
        return l->val == r->val && check(l->left, r->right) && check(l->right, r->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

t3 路径总和

依旧是递归。如果当前节点为空，那么说明整个遍历过程结束都没有达到suum，直接返回false；如果当前节点是叶子节点，则判断当前val是否等于sum值，如果是则返回true，除外直接递归遍历左右子树，返回二者之或。

值得注意的是，每次递归遍历用sum减去当前的val值，这样可以免除使用额外变量记录当前sum值的麻烦。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
       if(root == NULL) return false;

        if(root->left == NULL && root->right == NULL) return root->val == sum;

        return hasPathSum(root->left, sum - root->val) ||
               hasPathSum(root->right, sum - root->val); 
    }
};