二叉(搜索)树递归/迭代拓展（精选）

1.相同的树（100-易）

题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例：

输入：p = [1,2,3], q = [1,2,3]
输出：true

思路：如果两棵树相同，其子树也一定相同：树的结构和数值相同。

代码实现：

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (p.val != q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

延伸(T572/剑指26)：给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

思路：判断一棵树是否为另一棵树的子树。这样就是判断t的头结点与s所有子节点比较是否是相同的树。

代码实现：

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) {
        return false;
    }
    return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
    if (s == null && t == null) {
        return true;
    }
    if (s == null || t == null) {
        return false;
    }
    if (s.val != t.val) {
        return false;
    }
    return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}

2.对称二叉树（101-易）

题目描述：给定一个二叉树，检查它是否是镜像对称的。要求：迭代和递归。

示例：

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

思路：

• 递归：与上题相同，只不过我们递归的逻辑改变（不是两个子树的对应位置比较）
• 迭代：关键是如何入队，我们每次都能取出两个节点，一个代表左子树，另一个代表右子树。

代码实现：

// 递归
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
       return true; 
    }
    return dfs(root.left, root.right);
}

public boolean dfs(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (p.val != q.val) {
        return false;
    }
    return dfs(p.left, q.right) && dfs(p.right, q.left);
}

// 迭代
public boolean isSymmetric(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root.left);
    queue.add(root.right);

    while (!queue.isEmpty()) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();
        if (left == null && right == null) {
            continue;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}

2.翻转二叉树/镜像（226-易/剑指27）

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

思路：递归与迭代实现。

• 递归：进行递归翻转时，比如我们先翻转左子树，我们就要记录一下这个节点，方便翻转右子树。
• 迭代：每次从队列中拿出一个节点，交换这两个节点的左右子树。

代码实现：

// 递归
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode left = root.left;

    root.left = invertTree(root.right);
    root.right = invertTree(left);
    return root;
}

public boolean dfs(TreeNode p, TreeNode q) {
if (p == null && q == null) {
    return true;
}
if (p == null || q == null) {
    return false;
}
if (p.val != q.val) {
    return false;
}
return dfs(p.left, q.right) && dfs(p.right, q.left);
}

// 迭代
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        TreeNode left = cur.left;
        cur.left = cur.right;
        cur.right = left;

        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
    return root;
}

拓展（T951）：判断两树是否翻转等价。我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。

• 递归思路：本题是子树和翻转树的结合版，不满足子树直接返回false，否则，我们递归两种情况：子树或翻转树（因为我们不知道究竟是哪几个节点翻转了）

代码实现：

public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) {
        return true;
    }
    if (root1 == null || root2 == null || root1.val != root2.val) {
        return false;
    }
    return flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) ||
            flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
}

3.验证二叉搜索树（98-中）

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

思路：二叉搜索树中序（左中有）升序，中序遍历二叉搜索树。这里有一个技巧就是设置pre变量。

代码实现：

long pre = Long.MIN_VALUE;

public boolean isValidBST(TreeNode root) {
   if (root == null) {
       return true;
   } 
   if (!isValidBST(root.left)) {
       return false;
   }
   //访问当前节点，当前节点小于或者等于中序遍历的上一个节点不满足规则
   if (root.val <= pre) {
       return false;
   }
   pre = root.val;
   return isValidBST(root.right);
}

4.二叉搜索树的查找、插入与删除操作

题目描述：二叉搜索树中给定值的查找（T700）、插入（T701）和删除（T405）。保证结果任然是二叉搜索树。

查找：递归与迭代实现，利用二叉搜索树的性质。

• 注意：我们要返回值等于val的节点（子树），其余的都不要！！所以，对于遍历过程中，我们是直接返回即可，不需要像插入和删除一样进行连接

代码实现：

查找二叉搜索树给定值节点：

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || val == root.val) return root;
    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

插入：递归与迭代实现，利用二叉搜索树的性质。

• 递归函数终止条件，root == null， 创建节点插入（这种思路保证：插入节点一定在叶子节点）
• 迭代实现：与递归实现相同，定义一个cur指针遍历二叉搜索树，主要还是依靠bst树的性质。

代码实现：

// 递归 
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val > root.val) {
        root.right = insertIntoBST(root.right, val);
    } else if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    }
    return root;
}
// 迭代
public TreeNode insertIntoBST(TreeNode root, int val) {
    TreeNode node = new TreeNode(val);
    if (root == null) {
        return node;
    }
    TreeNode cur = root;
    while (cur != null) {
        if (val > cur.val) {
            if (cur.right == null) {
                cur.right = node;
                break;
            }
            cur = cur.right;
        } else {
            if (cur.left == null) {
                cur.left = node;
                break;
            }
            cur = cur.left;
        }
    }
    return root;
}

删除：根据二叉搜索树的性质，我们可以通过节点值大小，确定待删除节点的位置。一般情况，如果删除当前节点，分两种情况：

• 无左或者右子节点，删除该节点，对应的子树顶上
• 左右子节点都有，其左子树转移到其右子树的最左节点的子树上，然后右子树顶替其位置，由此删除了该节点。

注意：

• 递归函数返回的是删除该节点后的，顶替上来的根节点。
• 寻找左右子树的过程，我们没有删除，不能返回！

代码实现：

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else {
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        TreeNode node = root.right;
        // 寻找其右子树的最左节点
        while (node.left != null) {
            node = node.left;
        }
        node.left = root.left;
        root = root.right;
    }
    return root;
}

5.二叉搜索树中第K小的元素（230-中）

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

思路：定义一个count函数记录节点个数，根据二叉搜索树的性质，判断目标节点值。

代码实现：

public int kthSmallest(TreeNode root, int k) {
    int leftCount = count(root.left);
    if (leftCount == k - 1) {
        return root.val;
    }
    return leftCount < k - 1 ? 
           kthSmallest(root.right, k - leftCount - 1) : 
           kthSmallest(root.left, k);
}

private int count(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return count(node.left) + count(node.right) + 1;
}

延伸：剑指54，第k大的元素。同理

代码实现：

public int kthLargest(TreeNode root, int k) {
    int rightCount = count(root.right);
    if (rightCount == k - 1) {
        return root.val;
    }
    return rightCount < k - 1 ? 
           kthLargest(root.left, k - rightCount - 1) : 
           kthLargest(root.right, k);
}

private int count(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return count(node.left) + count(node.right) + 1;
}

6.左叶子之和（404-易）

计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

有两种递归的思路：

• 前序遍历：比较好理解的是利用前序遍历（判断当前节点是否为左叶子节点）。
• 自上向下递归：如果当前节点左子节点累积和（不要忘记递归右子树），再递归左右子树

// 前序遍历
private int ans = 0;;

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    inorder(root, false);
    return ans;
}

private void inorder(TreeNode node, boolean isLeft) {
    if (node == null) {
        return;
    }
    if (node.left == null && node.right == null && isLeft) {
        ans += node.val;
    }
    inorder(node.left, true);
    inorder(node.right, false);
}

// 自上向下递归
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (isLeaf(root.left)) {
        return root.left.val + sumOfLeftLeaves(root.right);
    } 
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

private boolean isLeaf(TreeNode node) {
    if (node == null) {
        return false;
    }
    return node.left == null && node.right == null;
}

7.二叉搜索树的最近公共祖先（235-易）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。注：一个节点本身也可以是自己的祖先。

思路：利用二叉搜索树的性质，本质是一个分治的过程，直接递归求解。注：一个节点本身也可以是自己的祖先。

迭代求解：迭代我们如何利用二叉搜索树性质呢，利用节点值的差值。如果在左子树或者右子树，那么当前节点值与这两个节点的差值乘积一定为正(即两个节点在同侧)。

// 递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
}
// 迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode cur = root;
    while ((cur.val - p.val) * (cur.val - q.val) > 0) {
        cur = cur.val > p.val ? cur.left : cur.right;
    }
    return cur;
}

进阶：二叉树的最近公共祖先（T236）

递归和迭代求解：

• 递归：作为上一题的进阶（上题我们通过比较较节点值大小确定左右子树的），这里我们任然需要处理这个问题。类似后续遍历，先遍历在左右子树的最近公共祖先，再判断当前位置。主要分为三种情况，见代码。

• 迭代（比较巧妙）：对于两个节点的公共祖先，root一定是他们的公共祖先但不是最近的，最近的应该是最开始的分叉节点。
  所以，我们可以倒序其中的一条路径，然后看当前路径在不在另一条路径上，当第一次出现这个节点就是最近的公共祖先。

（1）倒序一条路径的话：使用hashmap存储这个节点的父节点
（2）我们要查看两条路径有没有重合：使用hashset存储其中一个路径的节点值，方便判断
（3）如何找到这两个节点呢：我们使用一个栈结构，从root节点开始查找，当hashmap出现这两个节点的时候，停止，开始倒序。

代码实现：

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 root;
    }
    return left == null ? right : left;
}

// 迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Deque<TreeNode> stack = new LinkedList<>();
    Map<TreeNode, TreeNode> parents = new HashMap<>();
    stack.push(root);
    parents.put(root, null);

    while (!parents.containsKey(p) || !parents.containsKey(q)) {
        TreeNode cur = stack.pop();
        if (cur.left != null) {
            stack.push(cur.left);
            parents.put(cur.left, cur);
        }
        if (cur.right != null) {
            stack.push(cur.right);
            parents.put(cur.right, cur);
        }
    }

    HashSet<TreeNode> path = new HashSet<>();
    while (p != null) {
        path.add(p);
        p = parents.get(p);
    }

    while (q != null) {
        if (path.contains(q)) {
            break;
        }
        q = parents.get(q);
    }
    return q;
}

8.拓展（T1026）节点与其祖先节点的最大差值

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。返回这个最大值。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

思路：

• 题目解读：不管谁是谁的祖先，一个节点的最大差值，本质就是求解一条路径上的最大值与最小值的差值。

注意：路径的端点为任意节点！

代码实现：

private int ans = 0;

public int maxAncestorDiff(TreeNode root) {
    if (root == null) {
        return 0;
    }
    inorder(root, root.val, root.val);
    return ans;
}

private void inorder(TreeNode root, int max, int min) {
    if (root == null) {
        return;
    }
    min = Math.min(min, root.val);
    max = Math.max(max, root.val);

    ans = Math.max(Math.abs(max - min), ans);
    min = Math.min(min, root.val);
    max = Math.max(max, root.val);

    inorder(root.left, max, min);
    inorder(root.right, max, min);
}