leetcode——二叉树问题汇总

leetcode 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 void traversal(TreeNode cur, List<Integer> ans){if(cur == null) return;ans.add(cur.val);traversal(cur.left,ans);traversal(cur.right,ans);}public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root,ans);return ans;}
}

②迭代法：

/*** 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) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> ans = new ArrayList<>();if(root == null) return ans;stack.push(root);while(stack.size() != 0){TreeNode node = stack.pop();ans.add(node.val);if(node.right != null) stack.push(node.right);if(node.left != null) stack.push(node.left);}return ans;}
}

        LinkedList可以用于模拟栈和队列， push和pop可以用于模拟栈，add()和remove()可以用于模拟队列。

leetcode 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 void traversal(TreeNode cur, List<Integer> ans){if(cur == null) return;traversal(cur.left,ans);ans.add(cur.val);traversal(cur.right,ans);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root,ans);return ans;}
}

②迭代法： 

/*** 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) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> ans = new ArrayList<>();TreeNode cur = root;while(cur != null || stack.size() != 0){if(cur != null){stack.push(cur);cur = cur.left;//左}else{cur = stack.pop();ans.add(cur.val);//中cur = cur.right;//右}}return ans;}
}

leetcode 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 void traversal(TreeNode cur, List<Integer> ans){if(cur == null) return;traversal(cur.left,ans);traversal(cur.right,ans);ans.add(cur.val);}public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root,ans);return ans;}
}

leetcode 102. 二叉树的层序遍历

队列迭代法：

/*** 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<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if(root != null) queue.add(root);while(queue.size() != 0){int size = queue.size();List<Integer> list = new ArrayList<>();for(int i=0; i<size; i++){TreeNode node = queue.remove();list.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}ans.add(list);}return ans;}
}

leetcode 226. 翻转二叉树

        在层序遍历的代码上添加交换左右节点的逻辑即可： 

/*** 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 TreeNode invertTree(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();if(root != null) queue.add(root);while(queue.size() != 0){int size = queue.size();for(int i=0; i<size; i++){TreeNode node = queue.pop();//交换左右孩子节点TreeNode temp = node.left;node.left = node.right;node.right = temp;if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return root;}
}

leetcode 101. 对称二叉树

/*** 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 boolean isSymmetric(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root.left);queue.add(root.right);while(queue.size() != 0){TreeNode leftNode = queue.remove();TreeNode rightNode = queue.remove();if(leftNode == null && rightNode == null) continue;if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;queue.add(leftNode.left);queue.add(rightNode.right);queue.add(leftNode.right);queue.add(rightNode.left);}return true;}
}

leetcode 104. 二叉树的最大深度

        本题在层序遍历的代码上修改即可，每一层代表深度+1：

/*** 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 int maxDepth(TreeNode root) {if(root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();int ans = 0;queue.add(root);while(queue.size() != 0){int size = queue.size();ans++;for(int i=0; i<size; i++){TreeNode node = queue.remove();if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return ans;}
}

leetcode 111. 二叉树的最小深度

        大致思路和求二叉树最大深度类似，在内层while循环中加一句判断：当当前节点的左右节点都为空时，直接返回当前深度，此时也就是二叉树的最小深度。

/*** 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 int minDepth(TreeNode root) {if(root == null) return 0;int ans = 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size() != 0){int size = queue.size();ans++;for(int i=0; i<size; i++){TreeNode node = queue.remove();if(node.left == null && node.right == null) return ans;if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return ans;}
}

leetcode 222. 完全二叉树的节点个数

        用层序遍历的逻辑做即可：

/*** 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 int countNodes(TreeNode root) {int ans = 0;if(root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size() != 0){int size = queue.size();for(int i=0; i<size; i++){ans++;TreeNode node = queue.remove();if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return ans;}
}

leetcode 96. 不同的二叉搜索树

         本题利用动态规划来做，分析当n=3的情况：

• 当1作为根节点，此时左子树有0个节点，右子树有2两个节点，此时的二叉树种数应该有dp[0]*dp[2]种。
• 当2作为根节点，此时左右子树各有一个节点，种数都是dp[1]，此时的二叉树种数应该有dp[1]*dp[1]种。
• 当3作为根节点，此时情况和第一种情况类似，只是左右子树交换了。

class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i=2; i<=n; i++){for(int j=0; j<i; j++){dp[i] += dp[j] * dp[i-j-1];}}return dp[n];}
}