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