【算法】二叉树 binary tree

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