树的初始化

类包含左右节点属性以及val值。

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}

二叉树的中序遍历。

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();dfs(res,root);return res;}void dfs(List<Integer> res, TreeNode root) {if(root==null) {return;}//按照 左-打印-右的方式遍历dfs(res,root.left);res.add(root.val);dfs(res,root.right);}

二叉树的中序遍历2。

    public static List<Integer> inorderTraversal2(TreeNode root){//中序遍历List<Integer> res = new ArrayList<>();Deque<Object> stack = new LinkedList<>();if(root == null) return res;stack.push("WHITE");stack.push(root);while(!stack.isEmpty()){TreeNode node = (TreeNode)stack.pop();String color = (String)stack.pop();if (node == null) continue;if(color == "WHITE"){stack.push("WHITE");stack.push(node.right);stack.push("GRAY");stack.push(node);stack.push("WHITE");stack.push(node.left);}else{res.add(node.val);}}return res;}

翻转二叉树。

    public static TreeNode invertTree(TreeNode root) {//递归函数的终止条件，节点为空时返回if(root==null) {return null;}//下面三句是将当前节点的左右子树交换TreeNode tmp = root.right;root.right = root.left;root.left = tmp;//递归交换当前节点的 左子树invertTree(root.left);//递归交换当前节点的 右子树invertTree(root.right);//函数返回时就表示当前这个节点，以及它的左右子树//都已经交换完了return root;}

二叉树的最大深度

    public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}

测试类 生成了7种不一样的树。

    public static void main(String[] args) {//7个不同的树TreeNode root1 = null; // 空树TreeNode root2 = new TreeNode(1); // 只有根节点的树TreeNode root3 = new TreeNode(1); // 完全平衡二叉树root3.left = new TreeNode(2);root3.right = new TreeNode(3);root3.left.left = new TreeNode(4);root3.left.right = new TreeNode(5);TreeNode root4 = new TreeNode(1); // 非平衡二叉树root4.left = new TreeNode(2);root4.left.left = new TreeNode(3);root4.left.left.left = new TreeNode(4);root4.left.left.left.left = new TreeNode(5);TreeNode root5 = new TreeNode(1); // 只有左子树的树root5.left = new TreeNode(2);TreeNode root6 = new TreeNode(1); // 只有右子树的树root6.right = new TreeNode(2);TreeNode root7 = new TreeNode(1); // 多层深度的树root7.left = new TreeNode(2);root7.right = new TreeNode(3);root7.left.left = new TreeNode(4);root7.right.right = new TreeNode(5);invertTree(root7);System.out.println(inorderTraversal2(root7));}