---

方法

• 树的问题往往采用用递归解决，特定情形下才会用到栈（DFS）和队列（BFS）。
• 二叉搜索树中序递归遍历即为小到大的排序结果

---

注意点

• 切记每探查一个结点，都要先判断该位置是否存在结点。因为如果该位置结点不存在且没有判断时对其进行操作，会返回空指针异常。

---

目录

• 树的子结构
• 二叉搜索树的后序遍历序列
• 二叉树中和为某一值的路径（前序）
• 二叉搜索树与双向链表（中序）
• 二叉树的镜像
• 重建二叉树
• 对称的二叉树
• 二叉树的深度
• 平衡二叉树（后序最优）
• 二叉树的下一个结点
• 二叉搜索树的第k个结点（中序）

---

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

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

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

public boolean VerifySquenceOfBST(int [] sequence) {
    if (sequence == null || sequence.length == 0) {
        return false;
    }
    return helper(sequence, 0, sequence.length - 2, sequence.length - 1);
}
private boolean helper(int[] arr, int left, int right, int index) {
    if (left >= right) {
        return true;
    }
    int start = left, end = right;
    while (left < arr.length && arr[left] < arr[index]) {
        left++;
    }
    while (right >= 0 && arr[right] > arr[index]) {
        right--;
    }
    // 如果是后序遍历的数组，那么 left 指针刚好移动到 right 指针的右边
    if (right + 1 != left) {
        return false;
    }
    return helper(arr, start, right - 1, right) 
        && helper(arr, left, end - 1, end);
}

二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if (root == null) {
        return res;
    }
    list.add(root.val);
    target -= root.val;
    if (target == 0 && root.left == null && root.right == null) {
        res.add(new ArrayList<>(list));
    }
    FindPath(root.left, target);
    FindPath(root.right, target);
    // root节点左边右边目标路径找遍以后，就删掉list中的root节点，继续上层遍历
    list.remove(list.size() - 1);
    return res;
}

二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

• 二叉搜索树要转换成排序的双向链表，需要用中序递归遍历。在此基础上加入对头结点和遍历指针的处理即可。

private TreeNode head = null, p = null;
public TreeNode Convert(TreeNode pRootOfTree) {
    helper(pRootOfTree);
    return head;
}

private void helper(TreeNode node) {
    if (node == null) {
        return;
    }
    helper(node.left);
    if (head == null) {
        head = p = node;
    } else {
        p.right = node;
        node.left = p;
        p = node;
    }
    helper(node.right);
}

---

二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

源二叉树

            8
           /  \
          6   10
         / \  / \
        5  7 9  11

镜像二叉树

            8
           /  \
          10   6
         / \  / \
        11  9 7  5

public void Mirror(TreeNode root) {
    if (root == null) return;
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    Mirror(root.left);
    Mirror(root.right);
}

---

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    return helper(pre, 0, pre.length - 1, in, 0, in.length - 1);
}

private TreeNode helper(int [] pre, int preBegin, int preEnd,int [] in, int inBegin, int inEnd) {
    if (preBegin > preEnd || inBegin > inEnd) {
        return null;
    }
    TreeNode root = new TreeNode(pre[preBegin]);
    for (int i = inBegin; i <= inEnd; i++) {
        if (root.val == in[i]) {
            root.left = helper(pre, preBegin + 1, preBegin + i - inBegin, in, inBegin, i - 1);
            root.right = helper(pre, preBegin + i - inBegin + 1, preEnd, in, i + 1, inEnd);
            break;
        }
    }
    return root;
}

---

对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null) return true;
    return helper(pRoot.left, pRoot.right);
}

private boolean helper(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) {
        return true;
    }
    if (node1 == null || node2 == null) {
        return false;
    }
    return node1.val == node2.val
        && helper(node1.left, node2.right)
        && helper(node1.right, node2.left);
}

---

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

public int TreeDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}

---

平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

• 后序遍历二叉树，从下往上判断每个非叶子节点是否为平衡二叉树，然后返回树的深度，当遍历完根节点后，结果已经出来了，所有节点只需要遍历一次。

private boolean isBalance = true;
    
public boolean IsBalanced_Solution(TreeNode root) {
    if (root == null) return true;
    depth(root);
    return isBalance;
}

private int depth(TreeNode root) {
    if (root == null) return 0;
    int left = depth(root.left);
    int right = depth(root.right);
    if (Math.abs(left - right) > 1) {
        isBalance = false;
    }
    return Math.max(left, right) + 1;
}

二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

• 叶子结点：返回自身在左子 树 / 结点的第一个父结点
• 非叶子结点：如果有右子节点，返回右子树最左结点；如果没有右子节点，返回父节点

public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) return null;
    if (pNode.left == null && pNode.right == null) {
        while (pNode.next != null && pNode.next.right == pNode) {
            pNode = pNode.next;
        }
        return pNode.next;
    }
    if (pNode.right == null) {
        return pNode.next;
    }
    TreeLinkNode node = pNode.right;
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

---

二叉搜索树的第k个结点

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

• 二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。所以，按照中序遍历顺序找到第k个结点就是结果。

private int count = 0;
private TreeNode node;
TreeNode KthNode(TreeNode pRoot, int k) {
    if (pRoot == null) return node;
    KthNode(pRoot.left, k);
    count++;
    if (count == k) {
        node = pRoot;
    }
    KthNode(pRoot.right, k);
    return node;
}

---