遍历方式

• 深度优先遍历(一般采用递归或栈实现)

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

• 广度优先遍历(一般采用队列实现)

  • 层次遍历（迭代法）

代码实现

• Java定义树节点

  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 preorderTraversal(TreeNode root){ArrayList result = new ArrayList<>();//preorder(root,result); //前序遍历//inorder(root,result); //中序遍历postorder(root,result); //后序遍历return result;}public void preorder(TreeNode root, List result){// 前序遍历if(root==null){return;}result.add(root.val);preorder(root.left,result);preorder(root.right,result);}public void inorder(TreeNode root , List result){//中序遍历if(root==null){return;}inorder(root.left,result);result.add(root.val);inorder(root.right,result);}public void postorder(TreeNode root, List result){//后序遍历if(root==null){return;}postorder(root.left,result);postorder(root.right,result);result.add(root.val);}}

迭代使用栈替代递归

class Solution {public List preorderTraversal(TreeNode root) {// 前序遍历List result = new ArrayList<>();if (root == null) {return result;}Stack stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (root.right != null) {stack.add(root.right);}if (root.left != null) {stack.add(root.left);}}return result;}public List postorderTraversal(TreeNode root) {// 后序遍历,中左右，反转List result = new ArrayList<>();if (root == null) {return result;}Stack stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (root.left != null) {stack.add(root.left);}if (root.right != null) {stack.add(root.right);}}Collections.reverse(result);return result;}}

• 广度优先遍历（层次遍历）

  • 层次遍历

    将每一层依次入队，每一个节点出队都要让它的所有子节点入队。

    public List> levelOrder(TreeNode root){ArrayDeque queue = new ArrayDeque<>();ArrayList> result = new ArrayList<>();if(root==null){return result;}queue.addLast(root);while (!queue.isEmpty()){int size = queue.size();ArrayList layer = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.pollFirst();layer.add(node.val);if(node.left!=null){queue.add(node.left);}if(node.right!=null){queue.add(node.right);}}result.add(layer);}return result;}
    

• LeetCode练习题

  • 226. 翻转二叉树

    public TreeNode invertTree(TreeNode root) {//只需要将子节点左右反转即可// 前序遍历-栈实现if(root==null){return null;}Stack stack = new Stack<>();stack.add(root);while (!stack.isEmpty()){TreeNode node = stack.pop();TreeNode temp = node.left;node.left = node.right;node.right = temp;if(node.left!=null){stack.add(node.left);}if(node.right!=null){stack.add(node.right);}}return  root;
    }
    

  • 101. 对称二叉树

     public boolean compare(TreeNode left,TreeNode right){if(left==null && right!=null){return false;} else if (left != null && right == null) {return false;} else if(left==null && right==null){return true;} else if (left!=null && right!=null) {return left.val==right.val && compare(left.left,right.right) && compare(left.right,right.left);}return false;}public boolean isSymmetric(TreeNode root) {//两种解法 1、递归法:两个子树的 外侧树相等，内侧树相等if(root==null){return true;}return compare(root.left,root.right);}
    

    public boolean isSymmetric2(TreeNode root) {//2、队列法，每次进队2个节点，出队2个节点ArrayDeque deque = new ArrayDeque<>();if(root.left==null && root.right==null){return true;} else if(root.left!=null && root.right!=null){deque.add(root.left);deque.add(root.right);} else {return false;}while (!deque.isEmpty()){TreeNode node1 = deque.pollFirst();TreeNode node2 = deque.pollFirst();if(node2.val!=node1.val || (node1.left!=null && node2.right==null)||(node1.left==null && node2.right!=null)||(node1.right==null && node2.left!=null)||(node1.right!=null && node2.left==null)){return false;}if(node1.left!=null){deque.add(node1.left);deque.add(node2.right);}if(node1.right!=null){deque.add(node1.right);deque.add(node2.left);}}return true;}
    

104. 二叉树的最大深度

public int depth(TreeNode root){if(root==null){return 0 ;}int leftDepth = depth(root.left);int rightDepth = depth(root.right);return Math.max(leftDepth,rightDepth)+1;}public int maxDepth(TreeNode root) {//两种方法 ，一种是递归法，一种是层次遍历法// 递归法//return depth(root);// 层次遍历ArrayDeque deque = new ArrayDeque<>();deque.add(root);int count = 0 ;while (!deque.isEmpty()){int size = deque.size();for (int i = 0; i < size; i++) {TreeNode node = deque.pollFirst();if(node.left!=null){deque.add(node.left);}if(node.right!=null){deque.add(node.right);}}count++;}return count;}

111. 二叉树的最小深度

    public int minDepth(TreeNode root) {//这道题有坑，注意是叶子节点if(root==null){return 0;}if(root.left==null && root.right==null){return 1;}int leftMin = Integer.MAX_VALUE;int rightMin = Integer.MAX_VALUE;if(root.left!=null){leftMin = minDepth(root.left);}if(root.right!=null){rightMin = minDepth(root.right);}return Math.min(leftMin,rightMin)+1;}

110. 平衡二叉树

public int depth(TreeNode root){if(root==null){return  0 ;}int left = depth(root.left);int right = depth(root.right);return Math.max(left,right)+1;}public boolean isBalanced(TreeNode root) {if(root==null){return true;}int leftDepth = depth(root.left);int rightDepth = depth(root.right);if(Math.abs(leftDepth-rightDepth)>1){return false;}else {return isBalanced(root.left) && isBalanced(root.right);}}

路径和问题

257. 二叉树的所有路径

public List binaryTreePaths(TreeNode root) {//路径问题使用深度优先搜索，可以递归实现或者迭代实现// 迭代法:注意路径栈要和节点栈同行ArrayList res = new ArrayList<>();Stack stack = new Stack<>();Stack paths = new Stack<>();stack.add(root);paths.add(root.val+"");while(!stack.isEmpty()){TreeNode node = stack.pop();String path = paths.pop();if(node.left==null && node.right==null){res.add(path);}if(node.right!=null){stack.add(node.right);paths.add(path+"->"+node.right.val);}if(node.left!=null){stack.add(node.left);paths.add(path+"->"+node.left.val);}}return res;}

public void treePath(TreeNode root,ArrayList paths, ArrayList res){paths.add(root.val);if(root.left==null && root.right==null){StringBuffer sb = new StringBuffer();for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)+"->");}sb.append(paths.get(paths.size()-1));res.add(sb.toString());return;}if(root.left!=null){treePath(root.left,paths,res);paths.remove(paths.size()-1);}if(root.right!=null){treePath(root.right,paths,res);paths.remove(paths.size()-1);}
}
public List binaryTreePaths(TreeNode root) {//路径问题使用深度优先搜索，可以递归实现或者迭代实现// 递归实现ArrayList res = new ArrayList<>();ArrayList paths = new ArrayList<>();treePath(root,paths,res);return res;
}

如果要得到的是路径是数组而非字符串，可以使用下面的数组替代字符串，不过最大的问题是，注意传进去的是引用，所以需要深拷贝，先拷贝再操作，一定不动原来的数组：

public int pathSum(TreeNode root, int targetSum) {//先得到所有的路径，再前缀和法求解//这次使用迭代法ArrayList> res = new ArrayList<>();Stack stack = new Stack<>();Stack> paths = new Stack<>();stack.add(root);ArrayList f = new ArrayList<>();f.add(root.val);paths.add(f);while (!stack.isEmpty()){TreeNode node = stack.pop();ArrayList path_temp = paths.pop(); ArrayList path = new ArrayList<>(path_temp);if(node.left==null && node.right==null){res.add(new ArrayList<>(path));}if(node.right!=null){stack.add(node.right);//先拷贝再操作ArrayList rightNewPath = new ArrayList<>(path);rightNewPath.add(node.right.val);paths.add(rightNewPath);}if(node.left!=null){stack.add(node.left);//先拷贝再操作ArrayList leftNewPath = new ArrayList<>(path);leftNewPath.add(node.left.val);paths.add(leftNewPath);}} }

112. 路径总和

    boolean res = false;public void dfs(TreeNode root, int target ,ArrayList path){if(root==null){return;}path.add(root.val);if(root.left==null && root.right==null){int sum = 0;for (int a : path){sum+=a;}if(sum==target){res = true;}return;}if(root.right!=null){dfs(root.right,target,path);//注意回溯path.remove(path.size()-1);}if (root.left!=null){dfs(root.left,target,path);//注意回溯path.remove(path.size()-1);}}public boolean hasPathSum(TreeNode root, int targetSum) {// 采用递归法ArrayList path = new ArrayList<>();dfs(root,targetSum,path);return res;}

113. 路径总和 II

     public void dfs(TreeNode root, int target , ArrayList path,List> res){if(root==null){return;}path.add(root.val);if(root.left==null && root.right==null){int sum = 0;ArrayList temp = new ArrayList<>();for (int a : path){sum+=a;temp.add(a);}if(sum==target){res.add(temp);}return;}if(root.right!=null){dfs(root.right,target,path,res);//注意回溯path.remove(path.size()-1);}if (root.left!=null){dfs(root.left,target,path,res);//注意回溯path.remove(path.size()-1);}}public List> pathSum(TreeNode root, int targetSum) {// 采用递归法ArrayList path = new ArrayList<>();List> res = new ArrayList<>();dfs(root,targetSum,path,res);return res;}

654. 最大二叉树

public TreeNode buildTree(int[] nums, int left, int right) {if (left > right) {return null;}int maxIdx = left;for (int i = left; i <= right; i++) {if (nums[i] > nums[maxIdx]) {maxIdx = i;}}TreeNode root = new TreeNode(nums[maxIdx] );root.left = buildTree(nums, left, maxIdx - 1);root.right = buildTree(nums, maxIdx + 1, right);return root;}public TreeNode constructMaximumBinaryTree(int[] nums) {//递归法TreeNode root = buildTree(nums, 0, nums.length - 1);return root;}

617. 合并二叉树

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null && root2==null){return null;}if(root1==null){return root2;}if(root2==null){return root1;}TreeNode root = new TreeNode(root1.val + root2.val);root.left = mergeTrees(root1.left,root2.left);root.right = mergeTrees(root1.right,root2.right);return root;}

98. 验证二叉搜索树

class Solution {long prevalue = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {//要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。//有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了if(root==null){return true;}if(!isValidBST(root.left)){return false;}if(root.val<=prevalue){return false;}prevalue = (long)root.val;if(!isValidBST(root.right)){return false;}return true;}
}

236. 二叉树的最近公共祖先

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null || root.val==p.val || root.val==q.val){return root;}TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left!=null && right!=null){return root;}if(left==null && right!=null){return right;}if(left!=null && right==null){return left;}return null;}

235. 二叉搜索树的最近公共祖先

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null || p.val==root.val || q.val==root.val){return root;}if(p.val > root.val && q.valreturn root;}if(p.val < root.val && q.val > root.val){return root;}if(p.val > root.val && q.val>root.val){return lowestCommonAncestor(root.right,p,q);}if(p.valreturn lowestCommonAncestor(root.left,p,q);}return null;}

701. 二叉搜索树中的插入操作

public TreeNode insertIntoBST(TreeNode root, int val) {if(root==null){root = new TreeNode(val);return root;}if(root!=null && root.left==null && root.val>=val){root.left = new TreeNode(val);}if(root!=null && root.right==null && root.valroot.right = new TreeNode(val);}if(val<=root.val){insertIntoBST(root.left,val);}else {insertIntoBST(root.right,val);}return root;}

108. 将有序数组转换为二叉搜索树

    public TreeNode buildTree(int[] nums,int left,int right){if(left>right){return null;}int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = buildTree(nums,left,mid-1);root.right = buildTree(nums,mid+1,right);return root;}public TreeNode sortedArrayToBST(int[] nums) {return buildTree(nums,0,nums.length-1);}

538. 把二叉搜索树转换为累加树

public class lc538 {int preNode = 0;public void dfs(TreeNode root ){// 遍历顺序：右中左if(root==null){return ;}if(root.right!=null){dfs(root.right);}preNode += root.val;root.val = preNode;if(root.left!=null){dfs(root.left );}}public TreeNode convertBST(TreeNode root) {dfs(root);return root;}
}