算法——树（一）

1、中序遍历

递归

class Solution {
    List<Integer> ans=new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return ans;
    }
    public void inorder(TreeNode root){
        if(root!=null){
            inorder(root.left);
            ans.add(root.val);
            inorder(root.right);
        }
    }
}

　　迭代：利用栈

 1 class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         List<Integer> ans=new ArrayList<>();
 4         Deque<TreeNode> stack=new LinkedList<>();
 5         while(root!=null||!stack.isEmpty()){
 6 
 7             while(root!=null){
 8                 stack.push(root);
 9                 root=root.left;
10             }
11             root=stack.pop();
12             ans.add(root.val);
13             root=root.right;
14             
15         }
16         return ans;
17     }
18 }

2、两棵二叉树是否相同

 1 class Solution {
 2     public boolean isSameTree(TreeNode p, TreeNode q) {
 3         if(p==null&&q==null){
 4             return true;
 5         }else{
 6             if(p==null||q==null){
 7                 return false;
 8             }else{
 9                 if(p.val!=q.val){
10                     return false;
11                 }else{
12                     return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
13                 }
14             }
15         }
16     }
17 }

3、对称二叉树

 1 class Solution {
 2     public boolean isSymmetric(TreeNode root) {
 3         return helper(root,root);
 4 
 5     }
 6     public boolean helper(TreeNode root1,TreeNode root2){
 7         if(root1==null&&root2==null){
 8             return true;
 9         }else{
10             if(root1==null||root2==null){
11                 return false;
12             }else{
13                 if(root1.val!=root2.val){
14                     return false;
15                 }else{
16                     return helper(root1.left,root2.right)&&helper(root1.right,root2.left);
17                 }
18             }
19         }
20     }
21 }

4、二叉树的最大深度

1 class Solution {
2     public int maxDepth(TreeNode root) {
3         if(root==null)return 0;
4         else return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
5 
6     }
7 }

5、将有序数组转换为二叉搜索树

//选择升序序列的中间元素作为根节点
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int[] nums,int left,int right){
        TreeNode root=null;
        if(left<=right){
            int mid=left+(right-left)/2;
            root=new TreeNode(nums[mid]);
            root.left=helper(nums,left,mid-1);
            root.right=helper(nums,mid+1,right);
        }
        return root;
    }
}

6、判断给定二叉树是否为平衡二叉树

 1 class Solution {
 2     public boolean isBalanced(TreeNode root) {
 3         if(root==null)return true;
 4         else{
 5             if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){
 6                 return false;
 7             }else{
 8                 return isBalanced(root.left)&&isBalanced(root.right);
 9             }
10         }
11 
12     }
13     public int maxDepth(TreeNode root){
14         if(root==null)return 0;
15         return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
16     }
17 }

7、二叉树的最小深度

 1 class Solution {
 2     public int minDepth(TreeNode root) {
 3         if(root==null)return 0;
 4         else{
 5             int m1=minDepth(root.left);
 6             int m2=minDepth(root.right);
 7             if(root.left==null||root.right==null)return m2+m1+1;
 8             return Math.min(m1,m2)+1;
 9         }
10 
11     }
12 }