二叉树

阅读量：5235 次

发布时间：2019-06-14

本文共 11899 字，大约阅读时间需要 39 分钟。

1、递归

想到用递归。涉及到左右子树比较，或者对称性等需要挨个节点比较。

写好递归结束条件。递归结束条件一般是root==null或者root1==null&&root2==null

处理好边界条件。可能会在边界上踩坑，可以特事特办采用特殊条件过滤。

1.1 一个树的递归

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

要求返回值是list需要新建递归函数传入list

递归结束条件是node==null

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {        public List
     
       inorderTraversal(TreeNode root) {            LinkedList
      
        list = new LinkedList<>();            if(root == null){                return list;            }else {                inOrder(list,root);                return list;            }                    }                public void inOrder(List list,TreeNode root){            if(root == null){                return;            }            inOrder(list,root.left);            list.add(root.val);            inOrder(list,root.right);        }}

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/

特事特办

class Solution {    public int minDepth(TreeNode root) {        if(root == null){            return 0;        }        int left = minDepth(root.left);        int right = minDepth(root.right);                if(left == 0){            return right + 1;        }        if(right == 0){            return left +1;        }                return left<=right?left+1:right+1;            }}

https://leetcode-cn.com/problems/path-sum/submissions/

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean hasPathSum(TreeNode root, int sum) {        if(root==null ){            return false;        }                if(root.val == sum &&root.left==null && root.right==null){            return true;        }                int sub = sum-root.val;                boolean l = hasPathSum(root.left,sub);        boolean r = hasPathSum(root.right,sub);        return l||r;    }}

https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

不仅是二叉树N叉树照样可以递归。

/*// Definition for a Node.class Node {    public int val;    public List
     
       children;    public Node() {}    public Node(int _val,List
      
        _children) {        val = _val;        children = _children;    }};*/class Solution {    public List
       
         preorder(Node root) {        List
        
          list = new ArrayList<>();        pre(list,root);        return list;    }        public void pre(List
         
           list,Node root){        if(root == null){            return;        }        list.add(root.val);        for(Node node:root.children){            pre(list,node);        }        return;    }}

1.2 两个树的递归

　　两个树的递归未必就是让你去递归两个树，两个树的递归多是处理一棵树的左右子树的问题。

https://leetcode-cn.com/problems/same-tree/

退出条件是都为null

两个节点关于判null有四种情况，为了省事可以只写都不为null的情况

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

https://leetcode-cn.com/problems/symmetric-tree/submissions/

隐式的使用两个树的递归

注意是左和右比较

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isSymmetric(TreeNode root) {        if(root == null){            return true;        }else{            return isSymmetricSub(root,root);        }    }            public boolean isSymmetricSub(TreeNode root1,TreeNode root2){        if(root2==null && root2==null){            return true;        }                if(root1!=null && root2!=null){            if(root1.val==root2.val){                return isSymmetricSub(root1.left,root2.right)&&isSymmetricSub(root1.right,root2.left);            }else{                return false;            }        }else{            return false;        }    }}

https://leetcode-cn.com/problems/balanced-binary-tree/comments/

首先写出计算树的高度的一个树的递归方法。其次在判断换一个树是否是平衡二叉树的时候要转成左右子树递归判断。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isBalanced(TreeNode root) {        if(root == null){            return true;        }        boolean isLeft = isBalanced(root.left);        boolean isRight = isBalanced(root.right);        if(isLeft && isRight){                        int l = getHeight(root.left);            int r = getHeight(root.right);            if(Math.abs(l-r)>1){                return false;            }else{                return true;            }        }else{            return false;        }            }        public int getHeight(TreeNode root){        if(root == null){            return 0;        }        int l = getHeight(root.left);        int r = getHeight(root.right);                return l>=r?l+1:r+1;    }}

1.3 递归中干点别的事

https://leetcode-cn.com/problems/diameter-of-binary-tree/submissions/

要把问题转换成自己熟悉的问题，这一题的翻译后就是在二叉树中找到一个节点，使得该节点的左右子树高度之和最大。这一题实际上是求二叉树高度的变体，求左右子树的高度也就是求二叉树的高度。

在求解的递归过程中需要使用一个全局的对象保存最大值，所有这里传入了一个长度为1的数组

我第一次错误的地方在于只考虑到了根节点的左右子树没有考虑到应该针对所有节点

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public int diameterOfBinaryTree(TreeNode root) {        int[] res = new int[1];        deep(root,res);        return res[0];    }        public int deep(TreeNode root,int[] res){        if(root==null){            return 0;        }                int left = deep(root.left,res);        int right = deep(root.right,res);        res[0] = res[0]>=left+right?res[0]:left+right;                return left>=right?left+1:right+1;    }}

https://leetcode-cn.com/problems/validate-binary-search-tree/submissions/

　　思路和上一题类似，需要在递归函数中设置一个全局的对象用于比较

/** * 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) {        int[] pre = {-1};        boolean isValid = inOrder(pre,root);        return isValid;    }        public boolean inOrder(int[] pre,TreeNode root){        if(root == null){            return true;        }        boolean isValid;                boolean left =  inOrder(pre,root.left);        if(pre[0]==-1){            pre[0] = root.val;            isValid =  true;        }else{            if(pre[0] >= root.val){                pre[0] = root.val;                isValid =  false;            }else{                pre[0] = root.val;                isValid =  true;            }        }        boolean right =  inOrder(pre,root.right);        return isValid && left && right;    }}

2、非递归遍历

2.1 非递归前中

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/

　　用栈去模拟递归中的压栈与出栈。对前序和中序而言遍历整个树的思路是相同的，不同的是print的时机或者list.add的时机，这种相似性和递归的前序中序遍历树是相同的。对每一个树，沿着左子树一直往左走并入栈，当发现第一个左子树为空的节点的时候从栈里pop出一个节点并重复一直向左的过程。

class Solution {    public List
     
       inorderTraversal(TreeNode root) {        List
      
        list = new ArrayList<>();        Stack
       
         stack = new Stack<>();        TreeNode cur = root;                while(!stack.isEmpty() || cur!=null){           while(cur != null){               stack.push(cur);               cur = cur.left;           }                        cur = stack.pop();            list.add(cur.val);            cur = cur.right;                    }                return list;    }}

class Solution {    public List
     
       preorderTraversal(TreeNode root) {        List
      
        list = new ArrayList<>();        Stack
       
         stack = new Stack<>();        TreeNode cur = root;                while(!stack.isEmpty() || cur!=null){            while(cur!=null){                stack.push(cur);                list.add(cur.val);                cur = cur.left;            }                        cur = stack.pop();            cur = cur.right;    }                return list;}}

2.2 层次遍历及变体

　　https://leetcode-cn.com/problems/binary-tree-level-order-traversal/submissions/

　　单单使用队列就可以实现层次遍历，但是leetcode要求用一个嵌套的链表返回遍历后的结果所以就得费点劲。整体的框架是不变的，变的是需要把每一层的遍历结果用一个list保存起来，最后再用一个嵌套的List把所有的子list一起保存起来。

class Solution {    public List
     
      
       > levelOrder(TreeNode root) {        Queue
       
         queue =  new LinkedList
        
         ();        List
         
          
           > rList = new LinkedList<>(); queue.add(root); if(root == null){ return rList; } while(!queue.isEmpty()){ int count = queue.size(); List
           
             list = new LinkedList<>(); while(count>0){ TreeNode t = queue.poll(); list.add(t.val); if(t.left != null){ queue.add(t.left); } if(t.right != null){ queue.add(t.right); } count --; } rList.add(list); } return rList; }}

　　https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

　　采用层次遍历的思想，多了一个isOdd用来判断是奇数行还是偶数行

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {  public List
     
      
       > zigzagLevelOrder(TreeNode root) {        if(root == null){            return new ArrayList();        }        Queue
       
         queue =  new LinkedList
        
         ();        List
         
          
           > rList = new LinkedList<>(); queue.add(root); boolean isOdd = false; while (!queue.isEmpty()){ List
           
             list = new LinkedList<>(); int count = queue.size(); while (count>0){ TreeNode node = queue.poll(); list.add(node.val); if (node.left !=null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } count--; } if(isOdd){ Collections.reverse(list); } isOdd = !isOdd; rList.add(list); } return rList; }}

https://leetcode-cn.com/problems/cousins-in-binary-tree/submissions/

　　一个层次遍历的应用，我第一反应也想到了层次遍历，我考虑到层次遍历只能判断两个节点是否在同一层却不能判断两个节点是否有是兄弟节点，因此没用。后来想到可以前序遍历整棵树，判断x y是否是兄弟节点。把这两个思路结合一起：在层次遍历的时候判断x y是否是兄弟节点，如果不是再判断x y是否再同一层。

　　按理说判断应该是以层为单位，即判断x y是否在同一层与判断x y是否是兄弟节点同时进行，但同时进行实现起来比较困难，因而这是一种分开的思想。当遍历到第i层的时候，先判断i层节点的子节点是否同时有x y，如果没有再判断是否 x y在第i层，其实你到i层的时候，i-1层以及帮你确认了i-1层的节点没有同时有x y孩子节点的情况。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isCousins(TreeNode root, int x, int y) {        Queue
     
       queue = new LinkedList<>();        queue.add(root);        while (!queue.isEmpty()){            int count = queue.size();            LinkedList
      
        list = new LinkedList<>();            while (count>0){                count --;                TreeNode node = queue.poll();                int l = -1,r = -1;                if(node.left != null){                    l = node.left.val;                    queue.add(node.left);                }                if(node.right != null){                    r = node.right.val;                    queue.add(node.right);                }                if(l==x&&r==y || l==y&&r==x){                    return false;                }                list.add(node.val);            }            if(list.contains(x) && list.contains(y)){                return true;            }        }        return false;    }}