相关概念
满二叉树
一棵深度为 k 且有 个结点的二叉树称为满二叉树。
节点数 = 2^k - 1
完全二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
每一层从左到右都不缺失节点，完全二叉树一定是满二叉树。
二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
平衡二叉搜索树
平衡二叉搜索树（英语：Balanced Binary Tree）是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
作业题
递归法遍历二叉树
144. 二叉树的前序遍历
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); dfs(root, result); return result; } private void dfs(TreeNode node, List<Integer> result) { if (node == null) { return; } result.add(node.val); dfs(node.left, result); dfs(node.right, result); } }
94. 二叉树的中序遍历
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); dfs(root, result); return result; } private void dfs(TreeNode node, List<Integer> result) { if (node == null) { return; } dfs(node.left, result); result.add(node.val); dfs(node.right, result); } }
145. 二叉树的后序遍历
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); dfs(root, result); return result; } private void dfs(TreeNode node, List<Integer> result) { if (node == null) { return; } dfs(node.left, result); dfs(node.right, result); result.add(node.val); } }
迭代法遍历二叉树
后续再补充。。。
