二叉树自顶向下递归和自底向上递归
二叉树自顶向下递归
自顶向下(top-down)
- 和前序遍历紧密关联(根->左->右)
- 当前节点的情况依赖于其父节点的情况
- 考虑完父节点,再考虑当前节点
LeetCode 104. 二叉树的最大深度
class Solution {
int ans;
public int maxDepth(TreeNode root) {
ans = 0;
dfs(root, 0);
return ans;
}
// 自顶向下
public void dfs(TreeNode node, int depth) {
// 需要先执行这句
ans = Math.max(ans, depth);
if (node == null)
return;
dfs(node.left, depth+1);
dfs(node.right, depth+1);
}
}
LeetCode 226. 翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return null;
if (root.left == null && root.right == null)
return root;
TreeNode left = invertTree(root.right);
TreeNode right = invertTree(root.left);
root.left = left;
root.right = right;
return root;
}
}
LeetCode 111. 二叉树的最小深度
class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
int ans = Integer.MAX_VALUE;
if (root.left != null)
ans = Math.min(ans, minDepth(root.left));
if (root.right != null)
ans = Math.min(ans, minDepth(root.right));
return ans+1;
}
}
LeetCode 112. 路径总和
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null)
return false;
if (root.left == null && root.right == null)
return targetSum == root.val;
return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
}
}
LeetCode 404. 左叶子之和
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null)
return 0;
else
return dfs(root);
}
public int dfs(TreeNode node) {
int sum = 0;
if (node == null)
return sum;
if (node.left != null) {
if (isLeafNode(node.left)) {
sum += node.left.val;
}
else
sum += dfs(node.left);
}
if (node.right != null && !isLeafNode(node.right))
sum += dfs(node.right);
return sum;
}
public boolean isLeafNode(TreeNode node) {
return node.left == null && node.right == null;
}
}
二叉树自底向上递归
自底向上(bottom-up)
- 和后序遍历紧密关联(左->右->根)
- 当前节点的情况依赖于其所有子节点的情况
- 考虑完所有子节点,再考虑当前节点
LeetCode 104. 二叉树的最大深度
class Solution {
public int maxDepth(TreeNode root) {
return dfs(root);
}
// 自底向上
public int dfs(TreeNode node) {
if (node == null)
return 0;
int left = dfs(node.left);
int right = dfs(node.right);
return Math.max(left,right) + 1;
}
}
LeetCode 110. 平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
else
return Math.abs(dfs(root.left)-dfs(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
}
public int dfs(TreeNode node) {
if (node == null)
return 0;
else
return Math.max(dfs(node.left),dfs(node.right)) + 1;
}
}
LeetCode 100. 相同的树
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null)
return true;
if ( (p == null && q != null) || (p != null && q == null) )
return false;
if (p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
LeetCode 101. 对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null)
return true;
return isSymmetricNode(root.left, root.right);
}
public boolean isSymmetricNode(TreeNode l, TreeNode r) {
if (l == null && r == null)
return true;
if ( (l==null && r!=null) || (l!=null && r==null) )
return false;
if (l.val != r.val)
return false;
return isSymmetricNode(l.left, r.right) && isSymmetricNode(l.right, r.left);
}
}
原文地址:https://blog.csdn.net/Noob_f/article/details/135614369
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!