二叉树的性质

  1. 在二叉树的第i层上至少有2^i-1^个结点（i>=1）
  2. 深度为k的二叉树最多有2^k^-1个结点（k>=1）。
  3. 对任何一棵二叉树T，如果其终端结点数为n~0~，度为2的结点数为n~2~，则n~0~=n~2~+1。
  4. 二叉树结点的左右子结点下标别离为2 * i + 1和2 * i + 2。
  5. 一个具备n个节点的齐全二叉树,其叶子节点的个数n0为: n/2 向上取整，或者(n+1)/2 向下取整

档次遍历-BFS

递归

class Solution {    List<List<Integer>> res=new ArrayList<List<Integer>>();    public void helped(TreeNode root,int level){        if(res.size() == level)            res.add(new ArrayList<Integer>());        res.get(level).add(root.val);        if(root.left != null){            helped(root.left, level+1);        }        if(root.right != null){            helped(root.right, level+1);        }    }    public List<List<Integer>> levelOrder(TreeNode root) {        if(root == null)            return res;        helped(root,0);        return res;    }}

迭代

class Solution {       public List<List<Integer>> levelOrder(TreeNode root){        List<List<Integer>> res=new ArrayList<List<Integer>>();        if(root == null)            return res;        Queue<TreeNode> queue = new LinkedList<TreeNode>();        queue.add(root);        int level = 0;        while(!queue.isEmpty()){            res.add(new ArrayList<Integer>());            int length = queue.size();                        for(int i=0;i<length;i++){                TreeNode r=queue.remove();                res.get(level).add(r.val);                if(r.left != null)                    queue.add(r.left);                if(r.right != null)                    queue.add(r.right);            }            level++;        }        return res;      }}

前序遍历

递归

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

迭代

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

中序遍历

递归

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

迭代

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

后序遍历

递归

class Solution {    List<Integer> res=new ArrayList<Integer>();    public List<Integer> postorderTraversal(TreeNode root) {        after(root);        return res;    }    public void after(TreeNode root) {        if(root==null)            return;        after(root.left);        after(root.right);        res.add(root.val);    }}

迭代

class Solution {    public List<Integer> postorderTraversal(TreeNode root) {        List<Integer> res=new ArrayList<Integer>();        Stack<TreeNode> s=new Stack<TreeNode>();        TreeNode cur=root;        TreeNode last=null;        while(cur!=null || !s.isEmpty()){            while(cur!=null){                s.push(cur);                cur=cur.left;            }            cur=s.peek();            if(cur.right==null || cur.right==last){                res.add(cur.val);                s.pop();                last=cur;                cur=null;            }else{                cur=cur.right;            }        }        return res;    }}