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