关于java:二叉树的遍历

二叉树的性质

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;
    }
}