检查子树（一）

class Solution {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    //判断list与node开头的子树是否对应
    public boolean isSub(ListNode head, TreeNode node) {
        if (head == null) return true; //若head为空，说明判断完毕，相互对应
        if (node == null) return false; //若node为空，说明子树少于list，不对应

        //若head与node不相等，返回false
        if (head.val != node.val) return false;

        //left和right中有一个对应即可
        return isSub(head.next, node.left) || isSub(head.next, node.right);
    }
}

检查子树（二）

class Solution {
//    public static class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//
//        TreeNode(int x) {
//            val = x;
//        }
//    }

    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if (t2 == null) return true;
        if (t1 == null) return false;
        return isSub(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    public boolean isSub(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;

        if (t1.val != t2.val) return false;

        return isSub(t1.left, t2.left) && isSub(t1.right, t2.right);
    }
}

对称二叉树

class Solution {
	public boolean isSymmetric(TreeNode root) {
		if(root==null) {
			return true;
		}
		//调用递归函数，比较左节点，右节点
		return dfs(root.left,root.right);
	}
	
	boolean dfs(TreeNode left, TreeNode right) {
		//递归的终止条件是两个节点都为空
		//或者两个节点中有一个为空
		//或者两个节点的值不相等
		if(left==null && right==null) {
			return true;
		}
		if(left==null || right==null) {
			return false;
		}
		if(left.val!=right.val) {
			return false;
		}
		//再递归的比较 左节点的左孩子 和 右节点的右孩子
		//以及比较  左节点的右孩子 和 右节点的左孩子
		return dfs(left.left,right.right) && dfs(left.right,right.left);
	}
}

二叉搜索树的最近公共祖先

最近公共祖先的定义： 设节点 root 为节点 p,q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p,q 的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：

  • p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
  • p=root，且 q 在 root 的左或右子树中；
  • q=root，且 p 在 root 的左或右子树中；

本题给定了两个重要条件：① 树为 二叉搜索树 ，② 树的所有节点的值都是 唯一 的。根据以上条件，可方便地判断 p,q 与 root 的子树关系，即：

  • 若 root.val < p.val，则 p 在 root 右子树 中；
  • 若 root.val>p.val ，则 p 在 root 左子树 中；
  • 若 root.val=p.val ，则 p 和 root 指向 同一节点 。

解法一：迭代

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}

解法二：递归

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        if(root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

前序与中序遍历序列构造二叉树

public TreeNode createTree(int[] pre, int[] in, int pl, int inl, int inr) {
    if (inl > inr) {
        return null;
    }
    int i = inl;
    for (; i <= inr; i++) {
        if (in[i] == pre[pl]) {
            break;
        }
    }
    TreeNode node = new TreeNode(pre[pl]);
    node.left = createTree(pre, in, pl + 1, inl, i - 1);
    node.right = createTree(pre, in, pl + i - inl + 1, i + 1, inr);
    return node;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0 || inorder.length == 0) {
        return null;
    }

    return createTree(preorder, inorder, 0, 0, inorder.length - 1);
}

hhhhh