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. 二叉树后序遍历非递归的三种写法 (数据结构)