Attention : 本文使用Java代码示例
前序遍历-Pre-order Traversal
首先访问根节点，然后遍历左子树，最后遍历右子树。
image.png
算法实现代码示例：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode node) {
List<Integer> list = new LinkedList<Integer>();
Stack<TreeNode> rights = new Stack<TreeNode>();
while (node != null) {
list.add(node.val);
if (node.right != null) {
rights.push(node.right);
}
node = node.left;
if (node == null && !rights.isEmpty()) {
node = rights.pop();
}
}
return list;
}
public static void main(String[] args ){
TreeNode treeNode = new TreeNode(1);
treeNode.right = new TreeNode(2);
treeNode.right.left = new TreeNode(3);
Solution solution = new Solution();
List<Integer> list = solution.preorderTraversal(treeNode);
System.out.print(list);
}
}
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode node) {
List<Integer> list = new LinkedList<Integer>();
Stack<TreeNode> rights = new Stack<TreeNode>();
while(node != null) {
list.add(node.val);
if (node.right != null) {
rights.push(node.right);
}
node = node.left;
if (node == null && !rights.isEmpty()) {
node = rights.pop();
}
}
return list;
}
}
中序遍历-In-order Traversal
首先遍历左边子树，然后访问根节点，最后访问右子树
image.png
算法实现示例：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
后序遍历-Post-order Traversal
首先遍历左边子树，然后遍历右子树，最后访问根节点
算法代码示例;
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
image.png
接下来介绍一种级别顺序（ Level-order Traversal）的遍历
宽度优先搜索 （Breadth-First Search）
简称BFS
该算法从根节点开始，首先访问节点本身。然后遍历它的邻居，遍历它的第二级邻居，遍历它的第三级邻居，依此类推。
image.png
下面我们用递归解决树的一些问题：
通常，我们可以从上到下或从下到上递归地解决树问题。
“自上而下”的解决方案（"Top-down" Solution）
“自上而下”意味着在每个递归级别中，我们将首先访问节点以获得一些值，并在递归调用函数时将这些值传递给它的子节点。因此，“自上而下”的解决方案可以被视为一种前序遍历。具体来说，递归函数的top_down(root, params)工作方式如下：
1. return specific value for null node
2. update the answer if needed // answer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, params
5. return the answer if needed // answer <-- left_ans, right_ans
例如：：给定二叉树，找到它的最大深度。
我们知道根节点的深度是1。对于每个节点，如果我们知道节点的深度，我们就会知道它的子节点的深度。因此，如果我们在递归调用函数时将节点的深度作为参数传递，则所有节点都知道它们自身的深度。对于叶节点，我们可以使用深度来更新最终答案。这是递归函数的伪代码maximum_depth(root, depth)：
1. return if root is null
2. if root is a leaf node:
3. answer = max(answer, depth) // update the answer if needed
4. maximum_depth(root.left, depth + 1) // call the function recursively for left child
5. maximum_depth(root.right, depth + 1) // call the function recursively for right child
为了帮助理解，给出下面的图示：
image.png
示例代码如下：
private int answer; // don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
answer = Math.max(answer, depth);
}
maximum_depth(root.left, depth + 1);
maximum_depth(root.right, depth + 1);
}
“自下而上”的解决方案（""Bottom-up" Solution）
“自下而上”是另一种递归解决方案。在每个递归级别中，我们将首先为所有子节点递归调用函数，然后根据返回值和根节点本身的值得出答案。这个过程可以看作是一种后序遍历。通常，“自下而上”的递归函数bottom_up(root)将如下所示：
1. return specific value for null node
2. left_ans = bottom_up(root.left) // call function recursively for left child
3. right_ans = bottom_up(root.right) // call function recursively for right child
4. return answers // answer <-- left_ans, right_ans, root.val
我们从另外一个角度，对于树的某个节点，以这个节点为根，如何求它子树的最大深度？
如果我们知道的此节点的左子树最大深度是1，其右子树的最大深度为r，那么我们可以选择它们之间的最大值加上1来获得此节点为根的子树的最大深度。那是x = max(l, r) + 1。
这意味着对于每个节点，我们都可以这么做。因此，我们可以使用“自下而上”的解决方案来解决这个问题。这是递归函数的伪代码maximum_depth(root)：
1. return 0 if root is null // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1 // return depth of the subtree rooted at root
图示如下：
image.png
网友评论