基础知识[1]⁍

二叉树的定义⁍

1
2
3
4
5
6
7
8
9
10
11
12
public class TreeNode {
    int val;
  	TreeNode left;
  	TreeNode right;
  	TreeNode() {}
  	TreeNode(int val) { this.val = val; }
  	TreeNode(int val, TreeNode left, TreeNode right) {
    		this.val = val;
    		this.left = left;
    		this.right = right;
  	}
}

二叉树种类⁍

  • 满二叉树： 每一层都是满的，第k层有2k-1个节点

  • 完全二叉树： 最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h-1 个节点。

    优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

  • 二叉搜索树： 有 数值 ， 二叉搜索树是一个有序树 。

    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 它的左、右子树也分别为二叉排序树

    下面这两棵树都是搜索树

    img

  • 平衡二叉搜索树（AVL（Adelson-Velsky and Landis）树）

    • 它是一棵 空树 或它的左右两个子树的 高度差 的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    • C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

二叉树的存储方式⁍

二叉树可以链式存储，也可以顺序存储（用数组）。

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

二叉树的遍历方式⁍

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）：中左右
    • 中序遍历（递归法，迭代法）：左中右
    • 后序遍历（递归法，迭代法）：左右中
  • 广度优先遍历
    • 层次遍历（迭代法）

递归遍历⁍

递归算法三要素⁍
  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144. 二叉树的前序遍历⁍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    ArrayList<Integer> preOrderReverse(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        preOrder(root, result);
        return result;
    }

    // 1. 确定递归函数的参数和返回值，传入ArrayList记录节点都数值
    void preOrder(TreeNode root, ArrayList<Integer> result) {
        // 2. 终止条件，当前遍历的节点空了，那么本层递归就要要结束
        if (root == null) { 
            return;
        }
        // 3. 确定单层递归的逻辑，三种遍历方法就这里不一样
        result.add(root.val);           // 中
        preOrder(root.left, result);    // 左
        preOrder(root.right, result);   // 右
    }
}
94. 二叉树的中序遍历⁍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
145. 二叉树的后序遍历⁍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

迭代遍历⁍

用栈的方式实现

前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

144. 二叉树的前序遍历⁍

按顺序将节点入栈，入栈的同时输出到result，到空的时候出栈，找右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}

//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/

改掉二重循环

—— 出栈的时候把节点值加入result，要求中节点入栈后，先将右节点入栈，再将左节点入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        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;
    }
}
94. 二叉树的中序遍历⁍

按顺序将节点入栈，出栈的时候把值加入result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            // 若有右节点，证明它也是这一层的“中”节点
            // 若是最左的叶子节点，则返回Null，后面继续出栈
            root = root.right;
        }
        return res;
    }
}

145. 二叉树的后序遍历⁍

与中序的不同之处在于：

  • 中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
  • 后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。

因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。

  • 当访问完一棵子树的时候，我们用prev指向该节点。
  • 这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        
        //主要思想：
        //由于在某颗子树访问完成以后，接着就要回溯到其父节点去
        //因此可以用prev来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            //从栈中弹出的元素，左子树一定是访问完了的
            root = stack.pop();
            //现在需要确定的是是否有右子树，或者右子树是否访问过
            //如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时
            //说明可以访问当前节点
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
                prev = root;
                root = null;
            } else {
                //如果右子树没有被访问，那么将当前节点压栈，访问右子树
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

统一迭代法⁍

将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Deque<TreeNode> st = new LinkedList<TreeNode>();
        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;
    }
}

⭐ 广度优先：层序遍历⁍

102. 二叉树的层序遍历⁍

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

不要把输入当作数组，输入还是树结构！！

方法一：递归，记录树深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        levelDFS(root,0);
        return result;
    }

    public void levelDFS(TreeNode root, int level){
        if(root==null)
            return;
        if(result.size()<level+1){
            // 如果是新的一层，则加进结果
            List<Integer> itemList = new ArrayList<Integer>();
            result.add(itemList);
        }
        // 将root节点加进相应层
        result.get(level).add(root.val);
        levelDFS(root.left, level+1);
        levelDFS(root.right, level+1);


    }
}

方法二：迭代，可借助队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return result;
        //创建队列存访二叉树节点（注意类型是TreeNode！）
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        //先将第一个根节点加入队列
        que.offer(root);
        while(!que.isEmpty()){
            List<Integer> itemList = new ArrayList<Integer>();
            //将队列中的元素都加入列表
            int len = que.size();
            while(len>0){
                TreeNode curNode = que.poll();
                itemList.add(curNode.val);
                //将左右节点入队
                if(curNode.left!=null) que.offer(curNode.left);
                if(curNode.right!=null) que.offer(curNode.right);
                len--;
            }
            result.add(itemList);
        }

        return result;
    }

}

相关题：

⭐ 递归函数的返回值⁍

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

  • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（113.路径总和ii）
  • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
  • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112.路径总和 的情况）

搜索一条边的写法：

1
2
3
if (递归函数(root->left)) return ;

if (递归函数(root->right)) return ;

搜索整个树写法：

1
2
3
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;

⭐ 递归与叶子节点⁍

有些情况下，递归需要在叶子节点处终止，此时在递归左右子节点的时候判断是否为null

1
2
3
4
5
6
7
8
9
10
递归函数(root, ...){
    //...
    if (root.left == null && root.right == null) {
        //终止逻辑
    }
    //...
    if(root.left!=null) 递归函数(root.left, ...);
    if(root.right!=null) 递归函数(root.right, ...);
    //...
}

236. 二叉树的最近公共祖先⁍

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

img

1
2
3
4
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
// 输入和返回的类型都是TreeNode

思路

❌错解：

  • 分别记录先序遍历到p和q节点的路径，比对两个路径最后一个相同的节点

  • 该节点可能是最近公共祖先，但也有可能是最近公共祖先的左子节点！

    • 例：

      1
      2
      3
      [3,5,1,6,2,0,8,null,null,7,4]
      5
      1

✔️正解[2]：

遍历方式选择： 自底向上查找 --> 二叉树回溯 --> 后序遍历(最先处理的是叶子节点)

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

递归三部曲：

  • 确定递归函数返回值及参数

    如果遇到p或者q，就把q或者p返回，返回值不为空，就说明找到了q或者p。

  • 确定终止条件

    如果找到了 节点p或者q，或者遇到空节点，就返回。

  • 确定单层递归逻辑

    • 本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断

    • 需要遍历整棵树，用left和right接住左子树和右子树的返回值，再处理left与right逻辑

      • 如果left和right都为空，则返回left或者right都是可以的，也就是返回空。

      • 如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解

      • 如果left和right中有一个为空、一个不为空，就返回不为空的那个。

        236.二叉树的最近公共祖先1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件和返回值
        if (root == null || root == p|| root == q) {
            return root;
        }
        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 处理左右子树逻辑
        if (left == null && right == null) {    // 两个都空，返回空
            return left;
        } else if (left !=null && right != null) {  // 两个都不为空，返回根节点
            return root;
        } else if (left !=null ){   // 只有一个节点不为空，返回不为空的节点
            return left;
        } else {
            return right;
        }
    }
}

637. 二叉树的层平均值⁍

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

img

1
2
3
4
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

思路： 层序遍历

注意点：

  • 将sum写作double型，计算平均值时可以自动进行类型转换

  • 提前记录队列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<Double>();
        
        // 二叉树非空
        // 创建队列 层序遍历
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        // 根节点入队
        que.offer(root);
        while(!que.isEmpty()){
            double sum = 0; // 注意直接写为double类型
            int len = 0;
            int lenq = que.size(); //因为后面涉及到出队操作，所以提前记录que的长度

            while(len < lenq){
                // 出队
                TreeNode curNode = que.poll();
                // 加入当前节点
                sum += curNode.val;
                // 左右节点入队
                if(curNode.left!=null) que.offer(curNode.left);
                if(curNode.right!=null) que.offer(curNode.right);
                len++;
            }
            if (!que.isEmpty()) {
                
            }
            result.add(sum/lenq);
        }
        return result;
        
    }
}

104. 二叉树的最大深度⁍

给定一个二叉树，找出其最大深度。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

⭐ 思路一： 深度=自底而上–>后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int deepl = maxDepth(root.left);
        int deepr = maxDepth(root.right);
        // 返回更大的深度
        return deepl>deepr?(deepl+1):(deepr+1);

    }


}

思路二： 迭代法 层序遍历，记录深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class solution {
    /**
     * 迭代法，使用层序遍历
     */
    public int maxdepth(treenode root) {
        if(root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isempty()) {
            int size = deque.size();
            depth++;//记录深度
            for (int i = 0; i < size; i++) {
                treenode poll = deque.poll();
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

111. 二叉树的最小深度⁍

方法一： 递归法⁍

后序遍历

❌误区：

不能仿照二叉树的最大深度写如下代码：

1
2
3
int leftDepth = getDepth(node.left);
int rightDepth = getDepth(node.right);
return Math.min(leftDepth, rightDepth) + 1;

这个代码就犯了此图中的误区：

111.二叉树的最小深度

如果这么求的话，没有左孩子的分支会算为最短深度。

✔️正解

  • 左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
  • 右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1
  • 左右子树都不为空，按上面的写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int deepl = minDepth(root.left);
        int deepr = minDepth(root.right);
        if (root.left==null) {
            return deepr+1;
        }else if(root.right==null){
            return deepl+1;
        }else{
            return Math.min(deepl,deepr)+1;
        }
    }
}

方法二：迭代法⁍

判断如果是叶子节点，直接返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int minDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int deep = 0;
        while (!que.isEmpty()) {
            deep++; // 记录量
            int len = que.size();
            while(len>0){
                TreeNode curNode = que.poll();
                if (curNode.left==null&&curNode.right==null) {//是叶子节点
                    return deep;
                }
                if (curNode.left != null) que.offer(curNode.left);
                if (curNode.right != null) que.offer(curNode.right);
                len--; //千万不要忘！！！！！！！
            }
        }
        return deep; //最终的返回值！
    }
}

559. N 叉树的最大深度⁍

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化 表示 ，每组子节点由空值分隔（请参见示例）。（表示方法而已！）

⭐N叉树表示方法示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node {
    public int val;
    public List<Node> children;//List

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

思路：

和二叉树的最大深度类似，左右子节点变为遍历一个列表的孩子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        int maxd = 0;
        for (Node i: root.children) {
            int di = maxDepth(i);
            maxd = Math.max(maxd, di); 
        }
        return maxd+1;
    }
}

543. 二叉树的直径⁍

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

思路

长度 = 左子树深度 + 右子树深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxL = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        int deep = getDepth(root);
        return maxL;    
        
    }

    public int getDepth(TreeNode node){
        if (node == null) {
            return 0;
        }
        int deepl = getDepth(node.left);
        int deepr = getDepth(node.right);
        // 记录最长距离
        maxL = Math.max(maxL, deepl + deepr);
        return Math.max(deepl, deepr)+1;
    }
}

222. 完全二叉树的节点个数⁍

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

思路： 利用完全二叉树的性质

完全二叉树只有两种情况：

  • 满二叉树：可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1

  • 最后一层叶子节点没有满。

    • 分别递归左孩子，和右孩子，递归到某一深度一定会有

        1. 左孩子为满二叉树
        2. 右孩子为满二叉树

        然后依然可以按照满二叉树来计算。

完全二叉树获得深度只需要不断遍历左节点就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        // root.left为空时，说明只有一个节点即root，情况被包含进去了
        int depL = getDepth(root.left);
        int depR = getDepth(root.right);
        if (depL==depR) {//说明左子树是满二叉树
            //左子树+右子树+根节点
            return (1<<depL)-1 + countNodes(root.right) + 1; 
            //1<<depL-1 = (int)Math.pow(2, depL)-1
        }else{
            // 否则，左子树非满二叉树，右子树是满二叉树
            return (1<<depR)-1 + countNodes(root.left) + 1 ;
        }
    }

    public int getDepth(TreeNode root){
        int depth = 0;
        while(root != null){
            root = root.left;
            depth++;
        }
        return depth;
    }
}

时间复杂度：$O(\log^2 n)$

110. 平衡二叉树⁍

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路： 递归算深度，设置标志位-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (getDepth(root)==-1) {
            return false;
        }
        return true;

    }

    public int getDepth(TreeNode root){
        if (root==null) {
            return 0;
        }
        int dL = getDepth(root.left);
        int dR = getDepth(root.right);

        // 如果已经不是平衡树了，直接返回-1
        if (dL==-1 || dR==-1 || Math.abs(dL-dR)>1) {
            return -1;
        }

        return Math.max(dL, dR)+1;
    }
}

226. 翻转二叉树⁍

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

思路：

先序遍历/后序遍历二叉树，交换左右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {

  public TreeNode invertTree(TreeNode root) {
    if (root == null) {
      return root;
    }
    //后序遍历
    invertTree(root.left);
    invertTree(root.right);
    swapNode(root);
    return root;
  }

  public void swapNode(TreeNode root) {
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
  }
}

101. 对称二叉树⁍

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

示例 1：

img

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

思路

  • 相当于比较根节点的左子树和右子树
  • 后序遍历：
    • 左子树：左右中
    • 右子树：右左中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {

  public boolean isSymmetric(TreeNode root) {
    //树中节点数目在范围 [1, 1000] 内
    return biPostOrder(root.left, root.right);
  }

  public boolean biPostOrder(TreeNode rootL, TreeNode rootR) {
    if ((rootL == null && rootR != null) || (rootL != null && rootR == null)) {
      return false;
    }
    if (rootL == null && rootR == null) {
      return true;
    }
    if (rootL.val != rootR.val) {
      return false;
    }
    // if (rootL.val == rootR.val) {
    //   return true; 不可以直接判断！！要进底下递归
    // }
    return (
      biPostOrder(rootL.left, rootR.right) &&
      biPostOrder(rootL.right, rootR.left)
    );
  }
}

257. 二叉树的所有路径⁍

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

思路：

用先序遍历，在叶子节点处终止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  public List<String> paths = new ArrayList<>();

  public List<String> binaryTreePaths(TreeNode root) {
    findPath(root, "");
    return paths;
  }

  public void findPath(TreeNode root, String path) {
    path = path + "->" + String.valueOf(root.val);
    if (root.left == null && root.right == null) {
      paths.add(path.substring(2)); //去除开头的"->"
      return;
    }
    if (root.left != null) findPath(root.left, path);
    if (root.right != null) findPath(root.right, path);
  }
}

700. 二叉搜索树中的搜索⁍

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

递归法⁍

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    // 递归，利用二叉搜索树特点，优化
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

迭代法⁍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

  public TreeNode searchBST(TreeNode root, int val) {
    //节点数在 [1, 5000] 范围内

    while (root != null) {
      if (root.val == val) {
        return root;
      }
      if (root.val > val) {
        root = root.left;
      } else {
        root = root.right;
      }
    }
    return root;
  }
}

清楚定义就行

⭐ 构造二叉树⁍

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

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

例如，给出

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

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

思路

后序遍历：左右中

中序遍历：左中右

通过后序遍历，从后往前，可以确定根节点

然后通过中序遍历，确定左子树的大小

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

逻辑：

  • 后序找根root

    1. 遍历中序到根，确定左子树长度llen

    2. 后序中根据左子树长度，找到左子树的根

      root_l = post_start+llen-1;

    3. 算出后序中右子树起始位置
      post_start_r = post_start+llen;

      左子树起始即原来的起始位置

      post_start_l = post_start;

    4. 中序遍历再＋1得到右子树在中序遍历中的起始位置

      in_start_r = in_start+llen+1;

      左子树的起始位置即原来的起始位置

      in_start_l = in_start;

  • 右子树的根就是后序遍历中的下一个

    root_r = root-1;

终止：

通过后序的长度来判断元素个数

  • 没有元素：返回Null
  • 只剩一个元素（叶子节点），返回节点

image-20220222184650406

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree1(inorder, postorder, 0, 0, postorder.length-1);

    }

    public TreeNode buildTree1(int[] inorder, int[] postorder, int in_start, int post_start, int root) {
 
        if (root-post_start+1<1) {//没有元素了
            return null;
        }
        if (root-post_start+1==1) {//只剩一个元素（无左右节点了）
            return new TreeNode(postorder[root]);
        }

        TreeNode node = new TreeNode(postorder[root]); // 倒序创建根节点
        int llen = 0; //左子树长度
        for (int i = in_start; i < inorder.length ; i++) {
            if (inorder[i]==postorder[root]) {
                break;
            }
            llen++;
        }


        int root_l = post_start+llen-1;
        int root_r = root-1;
        int post_start_l = post_start;
        int post_start_r = post_start+llen;
        int in_start_l = in_start;
        int in_start_r = in_start+llen+1;


        node.left = buildTree1(inorder, postorder, in_start_l,  post_start_l, root_l);
        node.right = buildTree1(inorder, postorder, in_start_r, post_start_r, root_r);
        return node;
        
    }
}

105. 从前序与中序遍历序列构造二叉树⁍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree1(preorder, inorder, 0, 0, preorder.length-1);
    }


    public TreeNode buildTree1(int[] preorder, int[] inorder, int in_start, int root, int pre_end) {
        if (root>pre_end) {
            return null;
        }

        TreeNode node = new TreeNode(preorder[root]);

        if (root==pre_end) {
            return node;
        }

        int llen = 0;
        for (int i = in_start; i < inorder.length; i++) {
            if (inorder[i]==preorder[root]) {
                break;
            }
            llen++;
        }

        int in_start_l = in_start;
        int in_start_r = in_start+llen+1;
        int root_l = root+1;
        int root_r = root+llen+1;
        int pre_end_l = root+llen;
        int pre_end_r = pre_end; 

        node.left = buildTree1(preorder, inorder, in_start_l, root_l, pre_end_l);
        node.right = buildTree1(preorder, inorder, in_start_r, root_r, pre_end_r);
        return node;


        
    }
}

前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。

另一个方法 ： 图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

先遍历一遍中序的数组，以（值，下标）的形式存储到dict里，用的时候直接取出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int i=0;
        for (int value:inorder) {
            map.put(value,i);
            i++;
        }
        TreeNode root = helper(preorder, 0, inorder, 0, preorder.length-1);
        return root;
    }
    TreeNode helper(int[] preorder, int root, int[] inorder, int start, int end) {
        if (root > end) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);

        int p = map.get(preorder[root]); // 中序遍历中根节点的位置，据此划分左子树和右子树
        int leftLen = p - start;
        int left = root+1;
        int right = left+leftLen;
        node.left = helper(preorder, left, inorder, start, right-1);
        node.right = helper(preorder, right, inorder, start+leftLen+1, end);
        return node;
    }
}

108. 将有序数组转换为二叉搜索树⁍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

  public TreeNode sortedArrayToBST(int[] nums) {
    return buildTree(nums, 0, nums.length);
  }

  public TreeNode buildTree(int[] nums, int left, int right) {
    //左闭右开
    if (left > right - 1) {
      return null;
    }
    if (left == right - 1) {
      return new TreeNode(nums[left]);
    }

    int mid = (left + right) >> 1;

    TreeNode root = new TreeNode(nums[mid]);
    root.left = buildTree(nums, left, mid);
    root.right = buildTree(nums, mid + 1, right);

    return root;
  }
}

类似： 654. 最大二叉树

⭐ 109. 有序链表转换二叉搜索树⁍

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

思路：

链表–>数组–>二叉树？————额外的空间 ❌（也不是完全不行啦）

✔ 快慢指针找中间的节点

快指针一次移动2，慢指针一次移动1

最后快指针到达右端点或快指针的下一个节点是右端点时，慢指针就可以指向中间节点。

同时，没有必要“先”找到中间节点：我们可以使用 中序遍历 先构建了左子树，建立结束后，指针自然指向中间结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public ListNode helpHead;//重要！！不能直接放进去递归

  public TreeNode sortedListToBST(ListNode head) {
    helpHead = head;
    int len = getListLength(head);
    return helper(0, len);
  }

  public int getListLength(ListNode head) {
    int cnt = 0;
    while (head != null) {
      head = head.next;
      cnt++;
    }
    return cnt;
  }

  public TreeNode helper(int left, int right) {
    if (left > right - 1) return null;
    int mid = (left + right) >> 1;
    TreeNode root = new TreeNode();
    root.left = helper(left, mid);
    root.val = helpHead.val;
    helpHead = helpHead.next;
    root.right = helper(mid + 1, right);
    return root;
  }
}

⭐ 701. 二叉搜索树中的插入操作⁍

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

思路：

不需要改变二叉树结构

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
            return new TreeNode(val);
            
        if (root.val < val){
            root.right = insertIntoBST(root.right, val); // 递归创建右子树
        }else if (root.val > val){
            root.left = insertIntoBST(root.left, val); // 递归创建左子树
        }
        return root;
    }
}

450. 删除二叉搜索树中的节点⁍

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

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

示例 1:

img

1
2
3
4
5
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

思路

  • 假如要删除的节点为叶节点，直接删除
  • 假如要删除的节点左节点不为空但右节点为空，则直接用左节点替换当前节点
  • 假如要删除的节点右节点不为空但左节点为空，则直接用右节点替换当前节点
  • 最后要删除的节点左右均不为空，寻找右子树中最左节点，用这个最左节点（就是后继节点）替换当前节点，并且将最左节点从原位置删除。 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {

  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    return helper(root, key);
  }

  public TreeNode helper(TreeNode root, int key) {
    if (root == null) {
      return null;
    }
    if (root.val > key) {
      root.left = helper(root.left, key);
    } else if (root.val < key) {
      root.right = helper(root.right, key);
    } else {
      //找到了，删除
      if (root.left == null) return root.right; //左孩子空，直接补上右节点
      if (root.right == null) return root.left;
      //删除右子树的最左节点
      TreeNode tmp = root.right;
      while (tmp.left != null) {
        tmp = tmp.left; //找到最左节点
      }
      root.val = tmp.val; //赋值
      root.right = helper(root.right, tmp.val); //删除右子树最左节点的值
    }

    return root;
  }
}

449. 序列化和反序列化二叉搜索树⁍

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

思路

  • 序列化：后序遍历
  • 反序列化：最后一个节点是root，从后往前搜索第一个小于根节点的就是左子树的根
  • 编码：用4位十六进制编码会缩短空间
    • 十六进制转换为十进制： Integer.parseInt(String s, 16)
    • 十进制转换为4位十六进制（十六进制格式化）
      • String.format(“%04x”, num)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Codec {

    public StringBuilder sb = new StringBuilder(); //用StringBuilder拼接字符串更高效
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        postorder(root);
        return sb.toString();
    }

    public void postorder(TreeNode root) {
        if (root==null) {
            return;
        }
        postorder(root.left);
        postorder(root.right);
        sb.append(encode(root.val));
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //先将data转换为十进制数据
        int len = data.length()/4;//节点个数
        int[] nums = new int[len];//节点值
        for (int i = 0; i < len; i++) {
            nums[i] = decode(data.substring(4*i, 4*(i+1)));
        }
        //通过nums构造二叉树
        return buildTree(nums, 0, len-1);

    }

    public TreeNode buildTree(int[] nums,int start, int root) {
        //root代表根在nums中的下标
        //start标示树开始的下标
        if (root<start) {
            return null;
        }

        TreeNode node = new TreeNode(nums[root]);

        if (root==start) {
            return node;
        }

        int root_r = root-1;
        int root_l = start-1;//如果该树不存在，则会root_l<start_l，会返回null
        for (int i = root-1; i >= start; i--) {
            //倒序查找第一个<nums[root]的值
            if (nums[i]<=nums[root]) {
                root_l=i;
                break;
            }
        }
        int start_l = start;
        int start_r = root_l+1;
        node.left = buildTree(nums, start_l, root_l);
        node.right = buildTree(nums, start_r, root_r);
        return node;

    }


    public String encode(int val) {
        return String.format("%04x", val);
    }

    public int decode(String val){
        return Integer.parseInt(val,16);
    }
    
}
  • python简单编码版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Codec:
    def __init__(self):
        self.st = ""
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root == None:
            return ""
        self.postOrder(root)
        return self.st
        
    def postOrder(self, root):
        if not root:
            return
        self.postOrder(root.left)
        self.postOrder(root.right)
        self.st += self.encode(root.val)
    
    def encode(self, i: int):
        return str(i)+'#'
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return []
        nodes = self.decode(data)
        # 根节点在最后
        root_index = len(nodes) - 1
        print(nodes)
        def buildTree(root_index, start_index):
            if root_index < start_index:
                return
            
            node = TreeNode(nodes[root_index])

            left_start = start_index # 左子树的起始就是根的起始
            right_root = root_index - 1 # 右子树的根就是根左边一个
            # 左子树的根是倒序查找第一个小于根节点的数的下标
            left_root = root_index - 1
            while left_root >= start_index and nodes[left_root] > nodes[root_index]:
                left_root-=1
            right_start = left_root + 1
            node.left = buildTree(left_root, left_start)
            node.right = buildTree(right_root, right_start)

            return node
        return buildTree(root_index, 0)


        
    
    def decode(self, data):
        li = data.split('#')[:-1]
        return [int(e) for e in li]

617. 合并二叉树⁍

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

思路：递归

因为不知道两棵树的深度，所以一定是先序遍历，从根节点开始

  • 都不为空，相加，返回
  • 一个为空，一个不为空，返回一个
  • 两个都为空，返回null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1==null&&root2==null) {
            return null;
        }
        if (root1==null&&root2!=null) {
            return root2;
        }
        if (root2==null&&root1!=null) {
            return root1;
        }
        TreeNode node = new TreeNode(root1.val+root2.val);
        node.left = mergeTrees(root1.left, root2.left);
        node.right = mergeTrees(root1.right, root2.right);

        return node;

    }
}

  1. 代码随想录 (programmercarl.com) ↩︎

  2. 0236.二叉树的最近公共祖先-代码随想录 (programmercarl.com) ↩︎