二叉树算法学习

Posted Jul 19, 2024 Updated Jul 30, 2024

By Kurisu 32 min read

二叉树遍历

递归遍历

这是所有二叉树递归的题目离不开的基础，不同的遍历顺序决定了递归逻辑的顺序。

递归算法的三个要素：

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

先以前序遍历为例，走一遍这个流程：

确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入List来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void。
确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return。
确定单层递归的逻辑：前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值。

代码示例：

  
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

迭代遍历

其实递归根本上还是把函数的局部变量、参数值和返回地址等压入调用栈中，那我们也可以自己用栈实现这个过程。

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数仍然是以前序遍历为例：
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。先加入右孩子才能保证出栈的时候遵循的是中左右的顺序。

代码示例：

  
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右，方法风格会有一些不一样，主要是中序需要先找到最坐下的节点
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

也有一种统一的迭代方法，较为难理解，留以备用

代码示例：

  
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

层序遍历

问题：给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

使用队列进行辅助，弹出节点时，将其子节点加入队列，以此类推；还可以使用递归方法，递归方法就是记录每个节点的深度，将其加入到对应深度索引的数组里。

代码示例：

  
// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //BFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;

        if (resList.size() < deep) {
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}

二叉树属性

对称二叉树

问题：给你一个二叉树的根节点 root ，检查它是否轴对称。

递归三部曲：

递归方法需要返回布尔值，我们要比较的是轴对称的左右子树，故一个节点是不够用的，要采用两个TreeNode作为参数。
当遇到空节点或左右已经不匹配时，递归就该终止了，对于空节点，一个为空则需要返回false，全都为空则返回true；都不为空则比较值是否相等，不相等则应该返回false了。
之后就是要判断left.right和right.left以及left.left和right.right的值是否相等了，先判断左右，左右都为true，整个子树才为true。

代码示例：

  
    /**
     * 递归法
     */
    public boolean isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {

        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }

        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        // 比较外侧
        boolean compareOutside = compare(left.left, right.right);
        // 比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }

二叉树的最大深度

问题：给定一个二叉树，找出其最大深度，二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

该题也可使用层序遍历，我们在这里使用递归法，本题可以采用前序遍历或是后序遍历，前序求深度，后序求高度，但对于根节点来讲深度就是高度。后序较为好理解，先求左右节点高度，再对于中间节点取左右最大值+1即可；而对于前序涉及到一点回溯，主要是针对高度的回溯，我们需要一个值记录当前节点深度，又需要一个值记录最大深度。

代码示例：

  
class Solution {
    /**
     * 递归法，后序求高度
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

class Solution {
  /**
   * 递归法，前序求深度
   */
    int maxnum = 0;

    public int maxDepth(TreeNode root) {
        ans(root,0);
        return maxnum;
    }
    
    //递归求解最大深度
    void ans(TreeNode tr,int tmp){
        if(tr==null) return;
        tmp++;
        maxnum = maxnum<tmp?tmp:maxnum;
        ans(tr.left,tmp);
        ans(tr.right,tmp);
        tmp--;
    }
}

二叉树的最小深度

问题：给定一个二叉树，找出其最小深度最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

跟求最大深度比较相似，后序遍历需要注意的就是要对节点进行是否为叶子节点的判断，如果为叶子节点不能单纯地取左右最小再加一。

代码示例：

  
class Solution {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近叶子节点的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

class Solution {
    /**
     * 递归法（思路来自二叉树最大深度的递归法）
     * 该题求最小深度，最小深度为根节点到叶子节点的深度，所以在迭代到每个叶子节点时更新最小值。
     */
    int depth = 0;
    // 定义最小深度，初始化最大值
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        dep(root);
        return minDepth == Integer.MAX_VALUE ? 0 : minDepth;
    }
    void dep(TreeNode root){
        if(root == null) return ;
        // 递归开始，深度增加
        depth++;
        // 该位置表示递归到叶子节点了，需要更新最小深度minDepth
        if(root.left == null && root.right == null)
            minDepth = Math.min(minDepth , depth);
        dep(root.left);
        dep(root.right);
        // 递归结束，深度减小
        depth--;
    }
}

平衡二叉树

问题：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

递归三部曲：

这里是要比较左右子树的高度的，因此返回类型为int最佳，参数为当前节点。
当遍历到null节点时，递归就结束，该节点高度为0。
采用后续遍历，得到左右子树高度后，再对根节点进行判断是否为平衡二叉树。

需要注意的就是，如果发现不是平衡树，就应该返回-1开始结束判断了，所以如果左右节点高度返回为-1就不需要再多做判断了，直接继续返回-1即可。

代码示例：

  
class Solution {
   /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

二叉树的所有路径

问题：给定一个二叉树，返回所有从根节点到叶子节点的路径。

从这题开始，就慢慢地接触回溯法了。本题在遍历节点的同时，记录了当前正在执行方法的paths也就是我们需要的路径，这是和之前的递归有所不同的地方。

仍然是递归三部曲：

我们使用了额外的res数组存储最后的结果，所以递归方法不需要返回值，但参数包括TreeNode当前节点，路径集合paths以及返回结果集合res。
我们找到叶子节点就要开始进行处理了，所以叶子节点即左右孩子为null就是终止条件。
采用前序遍历，首先将当前节点加入paths，再进行左递归和右递归，回溯就是将刚刚加入的节点从paths中删除，再去找下一条路径的节点。

代码示例：

  
class Solution {
    /**
     * 递归法
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();// 存最终的结果
        if (root == null) {
            return res;
        }
        List<Integer> paths = new ArrayList<>();// 作为结果中的路径
        traversal(root, paths, res);
        return res;
    }

    private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
        paths.add(root.val);// 前序遍历，中
        // 遇到叶子结点
        if (root.left == null && root.right == null) {
            // 输出
            StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
            res.add(sb.toString());// 收集一个路径
            return;
        }
        // 递归和回溯是同时进行，所以要放在同一个花括号里
        if (root.left != null) { // 左
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) { // 右
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
    }
}

路径总和

问题：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

这题我自己写的时候是沿用上面一题的思路，记录路径进行计算和回溯。遇到的问题就是对于布尔型返回值的处理还不够灵活，我一开始的思路是找到符合条件路径就返回true，把树遍历完都还没找到也就是在方法最后加上return false，发现最后方法会一直返回最后这个false。解决的办法就是把返回值作为条件再次判断后才返回结果。

示例给出的是另一种写法，即不断累减targetsum，直至为0就说明找到了这条路径，相比之下更为简洁。

代码示例：

  
class solution {
   public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum(root.left, targetsum);
            if (left) {      // 已经找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum(root.right, targetsum);
            if (right) {     // 已经找到
                return true;
            }
        }
        return false;
    }
}

二叉树修改与构造

翻转二叉树

问题：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

我们仍然遵循递归三部曲的步骤：

递归首先是确定方法返回值和参数，该题对树进行操作即可，不需要返回值，我们是对一个节点的左右子节点进行互换，故参数为TreeNode即可。
再就是确认终止条件，当我们遍历到的节点为null时就终止。
最后确定递归逻辑部分，该题使用前序遍历或者后序遍历都可以，中序遍历会造成有的节点多次翻转，对中间节点进行左右孩子的互换。

代码示例：

  
class Solution {
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }
    public void invert(TreeNode node) {
        if(node == null)
            return ;
        TreeNode temp;
        temp = node.left;
        node.left = node.right;
        node.right = temp;
        invert(node.left);
        invert(node.right);
    }
}

从中序与后序遍历序列构造二叉树

问题：根据中序遍历和后序遍历构造二叉树

思路很简单，只需要不断根据后序遍历找到新的根节点，对原数组进行划分，注意要控制好边界情况就行，我采用了保持全闭区间来完成这道题。

代码示例：

  
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return getTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    public TreeNode getTree(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
        if(postorderStart > postorderEnd)
            return null;
        if(postorderStart == postorderEnd)
            return new TreeNode(postorder[postorderStart]);
        TreeNode root = new TreeNode(postorder[postorderEnd]);
        int rootIndex = 0;
        for(int i = 0; i < inorder.length; i++) {
            if(inorder[i] == postorder[postorderEnd])
                rootIndex = i;
        }

        int leftInorderStart = inorderStart;
        int leftInorderEnd = rootIndex - 1;
        int rightInorderStart = rootIndex + 1;
        int rightInorderEnd = inorderEnd;

        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (rootIndex - inorderStart - 1);
        int rightPostorderStart = leftPostorderEnd + 1;
        int rightPostorderEnd = postorderEnd - 1;
        
        root.left = getTree(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);
        root.right = getTree(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);

        return root;
    }
}

二叉搜索树的属性

验证二叉搜索树

问题：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：节点的左子树只包含小于当前节点的数、节点的右子树只包含大于当前节点的数、所有左子树和右子树自身必须也是二叉搜索树。

这里要注意的陷阱就是，不能单纯比较左右节点和根节点的值，题目要求的是整个子树的值都要满足条件。所以这题正确的做法是采用中序遍历，判断是否满足遍历的值递增。

代码示例：

  
class Solution {
    // 递归
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) {
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST(root.right);
        return right;
    }
}

二叉树公共祖先问题

二叉树的最近公共祖先

问题：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

后序遍历是一个天然的回溯，遍历左右节点后回到上层的根节点。本题思路就是如果递归到子节点有一个目标节点，就将目标节点返回给上层，直到递归到两个节点的返回值都为目标节点，这其中目标节点自身为公共祖先的情况已经被包括在内了。

代码示例：

  
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return commonAncestor(root, p, q);
    }
    public TreeNode commonAncestor(TreeNode cur, TreeNode p, TreeNode q) {
        TreeNode left = null;
        TreeNode right = null;
        if(cur == null || cur == p || cur == q)
            return cur;
        // 左
        if(cur.left != null)
            left = commonAncestor(cur.left, p, q);
        // 右
        if(cur.right != null)
            right = commonAncestor(cur.right, p, q);
        // 中
        if(left == null && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return cur;
        }
    }
}

二叉搜索树的修改与构造

删除二叉搜索树的节点

问题：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

这道题我本来是想使用void的方法直接对树进行操作，但非常奇怪的一点是，对节点的左右孩子进行修改以及对节点本身的值进行修改都是可以的，但假如是要更换节点本身替换掉比如把节点变为null或者是另一个节点就会出现问题，编译也不会报错。这仍然是值传递导致的，对于对象引用来说，传递的是引用的副本。这意味着方法内部的引用和外部的引用指向同一个对象。对对象属性的修改会影响到原始对象，因为无论是外部还是内部的引用都指向同一个对象。

代码示例：

  
class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return root;
    if (root.val == key) {
      if (root.left == null) {
        return root.right;
      } else if (root.right == null) {
        return root.left;
      } else {
        TreeNode cur = root.right;
        while (cur.left != null) {
          cur = cur.left;
        }
        cur.left = root.left;
        root = root.right;
        return root;
      }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
  }
}

修剪二叉搜索树

问题：给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。

这题和删除二叉搜索树很相似，但若是把问题想明白甚至可以更简单，当我们找到小于low的节点，他的左节点肯定都得删除，同理大于high的节点的右孩子一定也都是无法满足条件的。是比较巧妙的一题，但若是想不到统一用删除的逻辑也可以做出来这题。

代码示例：

  
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        // root在[low,high]范围内
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

学习, 算法

算法

This post is licensed under CC BY 4.0 by the author.

二叉树遍历

递归遍历

迭代遍历

层序遍历

二叉树属性

对称二叉树

二叉树的最大深度

二叉树的最小深度

平衡二叉树

二叉树的所有路径

路径总和

二叉树修改与构造

翻转二叉树

从中序与后序遍历序列构造二叉树

二叉搜索树的属性

验证二叉搜索树

二叉树公共祖先问题

二叉树的最近公共祖先

二叉搜索树的修改与构造

删除二叉搜索树的节点

修剪二叉搜索树

Trending Tags