二叉树自顶向下递归和自底向上递归

本文主要是介绍二叉树自顶向下递归和自底向上递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树自顶向下递归

自顶向下（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;elsereturn 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;}elsesum += 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;elsereturn 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;elsereturn 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);}
}