首页 > 代码库 > Chapter three Binary Tree & Divide Conquer（二叉树&分治）
Chapter three Binary Tree & Divide Conquer（二叉树&分治）
1.binary-tree-preorder-traversal（二叉树的前序遍历）根-左-右
给出一棵二叉树，返回其节点值的前序遍历。
非递归解法【要记住】：
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here Stack<TreeNode> stack = new Stack<TreeNode>(); ArrayList<Integer> preorder = new ArrayList<Integer>(); if (root == null) { return preorder; } stack.push(root); while (!stack.empty()) { TreeNode node = stack.pop(); preorder.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return preorder; } }
由于stack的先进后出特性要注意先push node.right 后push node.left。
递归解法：
public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> preorder = new ArrayList<Integer>(); traverse(root, preorder); return preorder; } private void traverse(TreeNode root, ArrayList<Integer> preorder) { if (root == null) { return; } preorder.add(root.val); traverse(root.left, preorder); traverse(root.right, preorder); } }
分治解法：
public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> preorder = new ArrayList<Integer>(); if (root == null) { return preorder; } ArrayList<Integer> left = preorderTraversal(root.left); ArrayList<Integer> right = preorderTraversal(root.right); preorder.add(root.val); preorder.addAll(left); preorder.addAll(right); return preorder; } }
add()和addAll()的区别和使用
2.binary-tree-inorder-traversal（二叉树的中序遍历）左-根-右
给出一棵二叉树,返回其中序遍历。
非递归解法【要记住】：
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Inorder in ArrayList which contains node values. */ public ArrayList<Integer> inorderTraversal(TreeNode root) { // write your code here Stack<TreeNode> stack = new Stack<TreeNode>(); ArrayList<Integer> inorder= new ArrayList<Integer>(); TreeNode curt = root; while (curt != null || !stack.empty()) { while (curt != null) { stack.push(curt); curt = curt.left; } curt = stack.pop(); inorder.add(curt.val); curt = curt.right; } return inorder; } }
curt的使用。
分治：
public class Solution { /** * @param root: The root of binary tree. * @return: Inorder in ArrayList which contains node values. */ public ArrayList<Integer> inorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> inorder = new ArrayList<Integer>(); if (root == null) { return inorder; } ArrayList<Integer> left = inorderTraversal(root.left); ArrayList<Integer> right = inorderTraversal(root.right); inorder.addAll(left); inorder.add(root.val); inorder.addAll(right); return inorder; } }
3.binary-tree-postorder-traversal（二叉树的后序遍历）左- 右- 根
给出一棵二叉树，返回其节点值的后序遍历。
迭代解法【要记住】：
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here Stack<TreeNode> stack = new Stack<TreeNode>(); ArrayList<Integer> postorder = new ArrayList<Integer>(); TreeNode prev = null; TreeNode curt = root; if (root == null) { return postorder; } stack.push(root); while (!stack.empty()) { curt = stack.peek(); if (prev == null || prev.left == curt || prev.right == curt) { if (curt.left != null) { stack.push(curt.left); } else if (curt.right != null) { stack.push(curt.right); } } else if (curt.left == prev) { if (curt.right != null) { stack.push(curt.right); } } else { postorder.add(curt.val); stack.pop(); } prev = curt; } return postorder; } }
curt和prev的使用。分三种情况讨论：沿着树向下遍历、从左向上遍历树和其他。
分治解法：
public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> postorder = new ArrayList<Integer>(); if (root == null) { return postorder; } ArrayList<Integer> left = postorderTraversal(root.left); ArrayList<Integer> right = postorderTraversal(root.right); postorder.addAll(left); postorder.addAll(right); postorder.add(root.val); return postorder; } }
4.maximum-depth-of-binary-tree（二叉树的最大深度）
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的距离。
分治解法：
public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ public int maxDepth(TreeNode root) { // write your code here if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; } }
遍历解法：
public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ private int depth = Integer.MIN_VALUE; public int maxDepth(TreeNode root) { // write your code here if (root == null) { return 0; } helper(root, 1); return depth; } private void helper(TreeNode root, int curtDepth) { if (root == null) { return; } if (curtDepth > depth) { depth = curtDepth; } helper(root.left, curtDepth + 1); helper(root.right, curtDepth + 1); } }
遍历解法一般都会有helper()函数帮助，需要全局变量depth记录最大深度。
5.binary-tree-paths（二叉树的所有路径）
给一棵二叉树，找出从根节点到叶子节点的所有路径。
分治解法：
public class Solution { /** * @param root the root of the binary tree * @return all root-to-leaf paths */ public List<String> binaryTreePaths(TreeNode root) { // Write your code here List<String> results = new ArrayList<String>(); if (root == null) { return results; } List<String> leftResults = binaryTreePaths(root.left); List<String> rightResults = binaryTreePaths(root.right); for (String result : leftResults) { results.add(root.val + "->" + result); } for (String result : rightResults) { results.add(root.val + "->" + result); } if (results.size() == 0) { results.add("" + root.val); } return results; } }
遍历解法：
public class Solution { /** * @param root the root of the binary tree * @return all root-to-leaf paths */ public List<String> binaryTreePaths(TreeNode root) { // Write your code here List<String> paths = new ArrayList<String>(); if (root == null) { return paths; } helper(root, String.valueOf(root.val), paths); return paths; } private void helper(TreeNode root, String path, List<String> paths) { if (root == null) { return; } if (root.left == null && root.right == null) { paths.add(path); return; } if (root.left != null) { helper(root.left, path + "->" + String.valueOf(root.left.val), paths); } if (root.right != null) { helper(root.right, path + "->" + String.valueOf(root.right.val), paths); } } }
6.
Chapter three Binary Tree & Divide Conquer（二叉树&分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。