4. 二叉树遍历

4.1. 定义

1// Definition for a binary tree node.
2struct TreeNode
3{
4  int val;
5  TreeNode *left;
6  TreeNode *right;
7  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};

4.2. 先序遍历

先序遍历是深度优先遍历（DFS）。

  • 递归

 1void preOrderRecur(TreeNode* T)
 2{
 3  if(!T) return;
 4  else
 5  {
 6    visit(T->val);
 7    preOrderRecur(T->left);
 8    preOrderRecur(T->right);
 9  }
10}

  • 非递归

 1void preOrderNonRecur(TreeNode* T)
 2{
 3  stack<TreeNode*> stk;
 4  while(T || !stk.empty())
 5  {
 6    while(T)
 7    {
 8      visit(T->val);
 9      stk.push(T);
10      T = T->left;
11    }
12    if(!stk.empty())
13    {
14      T = stk.top();
15      stk.pop();
16      T = T->right;
17    }
18  }
19}

4.3. 中序遍历

  • 递归

     1void inOrderRecur(TreeNode* T)
 2{
 3  if(!T) return;
 4  else
 5  {
 6    inOrderRecur(T->left);
 7    visit(T->val);
 8    inOrderRecur(T->right);
 9  }
10}

  • 非递归

 1void inOrderNonRecur(TreeNode* T)
 2{
 3  stack<TreeNode*> stk;
 4  while(T || !stk.empty())
 5  {
 6    while(T)
 7    {
 8      stk.push(T);
 9      T = T->left;
10    }
11    if(!stk.empty())
12    {
13      T = stk.top();
14      stk.pop();
15      visit(T->val);
16      T = T->right;
17    }
18  }
19}

4.4. 后序遍历

  • 递归

 1void postOrderRecur(TreeNode* T)
 2{
 3  if(!T) return;
 4  else
 5  {
 6    postOrderRecur(T->left);
 7    postOrderRecur(T->right);
 8    visit(T->val);
 9  }
10}

  • 非递归

    • 方法一：后序遍历顺序是：left - right - root；先序遍历顺序是：root - left - right。采用先序遍历的方式，用栈来存储节点（FILO），得到的是按 root - right - left 顺序遍历的临时结果；把临时结果逆序输出，就是后序遍历的结果。

     1vector<int> postOrderNonRecur(TreeNode* T)
 2{
 3  vector<int> res;
 4  stack<TreeNode*> nodePtr;
 5  if(T) nodePtr.push(T);
 6  while(!nodePtr.empty())
 7  {
 8    T = nodePtr.top();
 9    nodePtr.pop();
10
11    res.push_back(T->val);
12    if(T->left) nodePtr.push(T->left);
13    if(T->right) nodePtr.push(T->right);
14  }
15  reverse(res.begin(), res.end());
16  return res;
17}

    • 方法二：一个节点如果不存在右子树，则遍历完左子树之后可以直接访问该节点的值；如果存在右子树，用一个额外的栈（inNode）来临时保存该节点。访问完该节点的右子树之后，就从栈弹出该节点进行访问。

     1vector<int> postOrderNonRecur(TreeNode* T)
 2{
 3    vector<int> res;
 4    stack<TreeNode*> nodePtr;
 5    stack<TreeNode*> inNode;
 6    while(T || !nodePtr.empty())
 7    {
 8        while(T)
 9        {
10            nodePtr.push(T);
11            T = T->left;
12        }
13        T = nodePtr.top();
14        nodePtr.pop();
15
16        if(T->right)
17        {
18            inNode.push(T);
19            T = T->right;
20        }
21        else
22        {
23            res.push_back(T->val);
24            while(!inNode.empty() && T == inNode.top()->right)
25            // 访问完节点的右子树之后，就从栈弹出该节点进行访问
26            {
27                res.push_back(inNode.top()->val);
28                T = inNode.top();
29                inNode.pop();
30            }
31            T = NULL;
32        }
33    }
34    return res;
35}

4.5. 层次遍历

层次遍历是广度优先遍历（BFS）。

 1void layerTraversal(TreeNode* T)
 2{
 3  queue<TreeNode*> Q;
 4  if(T) Q.push(T);
 5  while(!Q.empty())
 6  {
 7    T = Q.front();
 8    Q.pop();
 9    visit(T->val);
10    if(T->left) Q.push(T->left);
11    if(T->right) Q.push(T->right);
12  }
13}

4.6. 实例

  • [LeetCode] Binary Tree Maximum Path Sum 最大路径和，路径连续但可以不经过根节点。Hint：路径有三种形式：在左子树中，在右子树中，跨越根节点。

    https://leetcode.com/problems/binary-tree-maximum-path-sum/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    int maxPathSum(TreeNode* root)
 5    {
 6        int res = INT_MIN;
 7        maxPathSumEndWithRoot(root, res);
 8        return res;
 9    }
10private:
11    int maxPathSumEndWithRoot(TreeNode* root, int& res) // 以 root 结尾的路径的最大和
12    {
13        if(root)
14        {
15            int sumEndWithLeft = maxPathSumEndWithRoot(root->left, res); // 以 root->left 结尾的路径的最大和
16            int sumEndWithright = maxPathSumEndWithRoot(root->right, res); // 以 root->right 结尾的路径的最大和
17            int sumEndWithRoot = root->val + max(0, max(sumEndWithLeft, sumEndWithright)); // 以 root 结尾的路径的最大和，必须包含根节点本身，最多包含左右节点中的一个
18
19            sumEndWithLeft = max(0, sumEndWithLeft);
20            sumEndWithright = max(0, sumEndWithright);
21            int sumCrossRoot = root->val + sumEndWithLeft + sumEndWithright;
22            // 以上三步等价于：int sumCrossRoot = root->val + max(0, max(sumEndWithLeft+sumEndWithright, max(sumEndWithLeft, sumEndWithright)));
23            // 通过根节点的路径有四种情况：只包含根节点、包含根节点+左节点、包含根节点+右节点、包含根节点+左节点+右节点
24
25            res = max(res, sumCrossRoot);
26            // sumCrossRoot 表示通过节点 root 的路径的最大和
27            // 这里没有比较 res 与左子树路径最大和、右子树路径最大和，是因为在计算 sumEndWithLeft、sumEndWithright 的过程中（第15、16行），已经更新了 res
28            // 函数 maxPathSumEndWithRoot 会遍历树的每一个节点，因此 res 会和所有路径的路径和进行比较。
29
30            return sumEndWithRoot;
31        }
32        else return 0;
33    }
34};

  • [LeetCode] Populating Next Right Pointers in Each Node II 建立层次右向指针。Hint：层次遍历的下一个节点就是当前节点的 next 指针所指。

    https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    Node* connect(Node* root)
 5    {
 6        if(!root) return root;
 7        queue<Node*> que;
 8        que.push(root);
 9        que.push(nullptr);
10        Node* head = nullptr;
11        while(!que.empty())
12        {
13            Node* p = que.front();
14            que.pop();
15            if(!head)
16            {
17                head = p;
18                if(!que.empty()) que.push(nullptr);
19            }
20            else
21            {
22                head->next = p;
23                head = p;
24            }
25            if(p)
26            {
27                if(p->left) que.push(p->left);
28                if(p->right) que.push(p->right);
29            }
30        }
31        return root;
32    }
33};

  • [LeetCode] Binary Tree Right Side View 二叉树右视图。Hint：层次遍历保存每层的最后一个节点。

    https://leetcode.com/problems/binary-tree-right-side-view

    \(\color{darkgreen}{Code}\)

     1## 方法一：双端队列
 2# Definition for a binary tree node.
 3# class TreeNode:
 4#     def __init__(self, val=0, left=None, right=None):
 5#         self.val = val
 6#         self.left = left
 7#         self.right = right
 8from collections import deque
 9class Solution:
10    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
11        if not root: return []
12        dq = deque([root])
13        view = []
14        while len(dq):
15            n = len(dq)
16            view.append(dq[-1].val)
17            ## 遍历每一层的节点
18            for i in range(n):
19                node = dq.popleft()
20                if node.left: dq.append(node.left)
21                if node.right: dq.append(node.right)
22        return view

     1## 方法二：普通队列，使用一个空节点作为每层结束的标记（更耗时）
 2# Definition for a binary tree node.
 3# class TreeNode:
 4#     def __init__(self, val=0, left=None, right=None):
 5#         self.val = val
 6#         self.left = left
 7#         self.right = right
 8class Solution:
 9    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
10        if not root: return []
11        from queue import Queue
12        que = Queue()
13        view = []
14        pre = root
15        que.put(root)
16        que.put(None)
17        while not que.empty():
18            node = que.get()
19            if node is None:
20                view.append(pre.val)
21                ## 遍历完整棵树
22                if que.empty(): break
23                ## 遍历完一层，插入新的标记
24                else:
25                    que.put(None)
26                    continue
27            pre = node
28            if node.left:
29                que.put(node.left)
30            if node.right:
31                que.put(node.right)
32        return view

  • [LeetCode] Invert Binary Tree 翻转二叉树。Hint：方法一，递归；方法二，深度优先遍历；方法三，广度优先遍历。

    https://leetcode.com/problems/invert-binary-tree/

    \(\color{darkgreen}{Code}\)

     1// 方法一：递归
 2
 3class Solution
 4{
 5public:
 6    TreeNode* invertTree(TreeNode* root)
 7    {
 8        if(root)
 9        {
10            swap(root->left, root->right);
11            invertTree(root->left);
12            invertTree(root->right);
13        }
14        return root;
15    }
16};

     1// 方法二：深度优先遍历
 2
 3class Solution
 4{
 5public:
 6    TreeNode* invertTree(TreeNode* root)
 7    {
 8        TreeNode* node = root;
 9        stack<TreeNode*> stk;
10        while(node || !stk.empty())
11        {
12            while(node)
13            {
14                stk.push(node);
15                node = node->left;
16            }
17            if(!stk.empty())
18            {
19                node = stk.top();
20                stk.pop();
21                swap(node->left, node->right);
22                node = node->left; // 翻转之后的左子树是原来的右子树
23            }
24        }
25        return root;
26    }
27};

     1// 方法三：广度优先遍历
 2
 3class Solution
 4{
 5public:
 6    TreeNode* invertTree(TreeNode* root)
 7    {
 8        queue<TreeNode*> qe;
 9        if(root) qe.push(root);
10        while(!qe.empty())
11        {
12            TreeNode* node = qe.front();
13            qe.pop();
14            swap(node->left, node->right);
15            if(node->left) qe.push(node->left);
16            if(node->right) qe.push(node->right);
17        }
18        return root;
19    }
20};

  • [LeetCode] Balanced Binary Tree 平衡二叉树。Hint：后序遍历，在判断子树是否平衡的同时，保存子树的高度，避免重复计算。

    https://leetcode.com/problems/balanced-binary-tree/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    bool isBalanced(TreeNode* root)
 5    {
 6        int height = 0;
 7        return isBalanced(root, height);
 8    }
 9private:
10    bool isBalanced(TreeNode* root, int& height)
11    {
12        if(!root)
13        {
14            height = 0;
15            return true;
16        }
17        int leftHeight;
18        int rightHeight;
19        if(isBalanced(root->left, leftHeight) && isBalanced(root->right, rightHeight))
20        {
21            if(abs(leftHeight - rightHeight) <= 1)
22            {
23                height = max(leftHeight, rightHeight) + 1;
24                return true;
25            }
26        }
27        return false;
28    }
29};

  • [LeetCode] House Robber III 不包含相邻元素的最大路径和。Hint：后序遍历；包含或不包含头节点。

    https://leetcode.com/problems/house-robber-iii/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    int rob(TreeNode* root)
 5    {
 6        int inclu_root = 0; // 包含头节点的最大和
 7        int exclu_root = 0; // 不包含头节点的最大和
 8        return rob(root, inclu_root, exclu_root);
 9    }
10private:
11    int rob(TreeNode* root, int& inclu_root, int& exclu_root)
12    {
13        if(!root) return 0;
14        int inclu_left = 0, exclu_left = 0;
15        rob(root->left, inclu_left, exclu_left);
16        int inclu_right = 0, exclu_right = 0;
17        rob(root->right, inclu_right, exclu_right);
18        inclu_root = root->val + exclu_left + exclu_right;
19        exclu_root = max(inclu_left, exclu_left) + max(inclu_right, exclu_right);
20        return max(inclu_root, exclu_root);
21    }
22};

  • [LeetCode] Path Sum III 路径和为目标值。Hint：先序遍历，把每个节点当做起始节点。

    https://leetcode.com/problems/path-sum-iii/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    int pathSum(TreeNode* root, int sum)
 5    {
 6        int cnt = 0;
 7        traverse(root, sum, cnt);
 8        return cnt;
 9    }
10private:
11    void traverse(TreeNode* root, int target, int& cnt)
12    {
13        if(root)
14        {
15            getSumFromRoot(root, target - root->val, cnt); // 以 root 为起点的路径和
16            traverse(root->left, target, cnt);
17            traverse(root->right, target, cnt);
18        }
19    }
20    void getSumFromRoot(TreeNode* root, int target, int& cnt)
21    {
22        if(target == 0) cnt ++;
23        // 当后续路径和为 0，也是一条满足要求的路径，因此当 target 减到 0 之后不能立即返回，也需要继续遍历。
24        if(root->left) getSumFromRoot(root->left, target - root->left->val, cnt);
25        if(root->right) getSumFromRoot(root->right, target - root->right->val, cnt);
26    }
27};

  • [LeetCode] Lowest Common Ancestor of A Binary Tree 二叉树的最近公共祖先。Hint：后序遍历，两个节点在同一子树中，或有一个是根节点。

    https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
 5    {
 6        if(!root || !p || !q) return root;
 7        TreeNode* res = nullptr;
 8        postOrderTraversal(root, p, q, res);
 9        return res;
10    }
11private:
12    // 返回值表示：p 或 q 在 root 的子树中（包括根节点root）
13    bool postOrderTraversal(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode* &res)
14    {
15        if(!root) return false;
16        if(res) return false; // 已经有结果了，后面不需要再遍历了
17        bool lson = postOrderTraversal(root->left, p, q, res);
18        bool rson = postOrderTraversal(root->right, p, q, res);
19        if((lson && rson) || ((root == p || root == q) && (lson || rson))) res = root;
20        return lson || rson || root == p || root == q;
21    }
22};

4.7. 参考资料

  1. 二叉树后序遍历非递归的三种写法 (数据结构)