[LeetCode] 100. Same Tree 相同的树 leetcode java

题目:

给定两个二叉树,编写一个函数来检验它们是否相同。

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

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

思路:

先序遍历的同时,比较两棵树的节点值是否相同,不同返回false,也要判断p树左树空而q树左树不空的情况。

再有就是两棵空树 在一开始要先做判断。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null&&q == null)
            return true;
        if(p == null||q == null)
            return false;
        return (p.val == q.val) && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

[LeetCode] 99. Recover Binary Search Tree 恢复二叉搜索树 leetcode java

题目:

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

  • 使用 O(n) 空间复杂度的解法很容易实现。
  • 你能想出一个只使用常数空间的解决方案吗?

思路:

中序遍历二叉树,出现的节点的值会升序排序,如果有两个节点位置错了,那肯定会出现降序。设置一个pre节点指针,记录当前节点中序遍历时的前节点,如果当前节点小于pre节点的值,说明需要调整次序。如果在中序遍历时节点值出现了两次降序,第一个错误的节点为第一次降序时较大的节点,第二个错误节点为第二次降序时较小的节点。比如,原来的搜索二叉树在中序遍历的节点值依次为{1,2,3,4,5},如果因为两个节点位置错了而出现{1,5,3,4,2},第一次降序为5->3,所以第一个错误节点为5,第二次降序为4->2,所以第二个错误节点为2,将5和2换过来就可以恢复。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode pre;
    TreeNode first;
    TreeNode second;
      
    public void inorder(TreeNode root){  
        if(root == null)  
            return;  

        inorder(root.left);  
        if(pre == null){  
            pre = root;  //pre指针初始
        }else{  
            if(pre.val > root.val){  
                if(first == null){  
                    first = pre;//第一个逆序点
                }  
                second = root;  //不断寻找最后一个逆序点
            }  
            pre = root;  //pre指针每次后移一位
        }  
        inorder(root.right);  
    }  
      
    public void recoverTree(TreeNode root) {  
        pre = null;  
        first = null;  
        second = null;  
        inorder(root);  
        if(first!=null && second!=null){   
            int tmp = first.val;  
            first.val = second.val;  
            second.val = tmp;  
        }  
    }
}

[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 leetcode java

题目:

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

一个二叉搜索树具有如下特征:

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ,但是其右子节点值为 4 。

思路:

二叉查找树有一个重要的性质:即中序遍历递增(不存在两个节点值相等),根据此,中序遍历完成后,查看序列是否有序即可知道是否是二叉查找树。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
		ArrayList<Integer> pre = new ArrayList<Integer>();
		pre.add(null);
		return helper(root, pre);
	}

	private boolean helper(TreeNode root, ArrayList<Integer> pre) {
		if (root == null)
			return true;

		boolean left = helper(root.left, pre);

		if (pre.get(pre.size() - 1) != null && root.val <= pre.get(pre.size() - 1))
			return false;
		pre.add(root.val);
		boolean right = helper(root.right, pre);
		return left && right;
	}
}