LeetCode-二叉树

二叉树的遍历,注意递归和非递归两种思路。

94. Binary Tree Inorder Traversal 二叉树中序遍历

https://leetcode.com/problems/binary-tree-inorder-traversal/

题目:给定二叉树,返回节点值的中序遍历。

思路:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        inShow(list, root);
        return list;
    }
    
    public void inShow(List<Integer> l, TreeNode node) {
        if(node.left != null) {
            inShow(l, node.left);
        }
        l.add(node.val);
        if(node.right != null) {
            inShow(l, node.right);
        }
    }
}

100. Same Tree 相同的树

https://leetcode.com/problems/same-tree/

题目:给定两个二叉树,编写一个函数来检查它们是否相同。如果两个二叉树在结构上相同,且节点具有相同的值,则它们被认为是相同的。

思路:

①:判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理,利用深度优先搜索DFS来递归。

②:还有非递归的解法,因为二叉树的四种遍历(层序,先序,中序,后序)均有各自的迭代和递归的写法,这里我们先来看先序的迭代写法,相当于同时遍历两个数,然后每个节点都进行比较。

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) || (p.val != q.val)) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

129. Sum Root to Leaf Numbers 求根节点到叶节点的值的总和

http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

题目:如果一个二叉树只包含从0到9的数字,那么每个根到叶的路径都可以表示一个数字.一个例子是根对叶路径1->2->3,它表示数字123。找出所有根到叶数的总和。注意:叶子是一个没有子节点的节点。

思路:

class Solution {
    int tot = 0;
    public int sumNumbers(TreeNode root) {
        if(root==null)
            return 0;
        calc(root,0);
        return tot;
    }
    
    public void calc(TreeNode root, int currsum) {
        currsum =currsum*10 + root.val;
        if(root.left==null && root.right==null){
            tot+=currsum;
            return;
        }
        if(root.left!=null)
            calc(root.left,currsum);
        if(root.right!=null)
            calc(root.right,currsum);
        return;
    }
}

144. Binary Tree Preorder Traversal 二叉树前序遍历

https://leetcode.com/problems/binary-tree-preorder-traversal/

题目:给定二叉树,返回其节点值的前序遍历。

思路:

class Solution {
    // 递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        frontShow(list, root);
        return list;
    }
    
    public void frontShow(List<Integer> l, TreeNode node) {
        l.add(node.val);
        if(node.left != null) {
            frontShow(l, node.left);
        }
        if(node.right != null) {
            frontShow(l, node.right);
        }
    }
}
class Solution {
    // 非递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        Stack<TreeNode> rights = new Stack<TreeNode>();
        while(root != null) {
            list.add(root.val);
            if(root.right != null) {
                rights.push(root.right);
            }
            root = root.left;
            if(root == null && !rights.isEmpty()) {
                root = rights.pop();
            }
        }
        return list;
    }
}

145. Binary Tree Postorder Traversal 二叉树后序遍历

https://leetcode.com/problems/binary-tree-postorder-traversal/

题目:给定二叉树,返回节点值的后序遍历。

思路:

class Solution {
    // 递归实现
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        backShow(list, root);
        return list;
    }
    
    public void backShow(List<Integer> l, TreeNode node) {
        if(node.left != null) {
            backShow(l, node.left);
        }
        if(node.right != null) {
            backShow(l, node.right);
        }
        l.add(node.val);
    }
}

// TODO

遍历变种:http://oj.leetcode.com/problems/path-sum/
遍历变种:http://oj.leetcode.com/problems/path-sum-ii/
遍历变种:http://oj.leetcode.com/problems/maximum-depth-of-binary-tree/
遍历变种:http://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
重建二叉树:http://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
重建二叉树:http://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
层次遍历变种:http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
遍历变种:http://oj.leetcode.com/problems/symmetric-tree/
遍历应用:http://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
遍历应用:http://oj.leetcode.com/problems/balanced-binary-tree/
遍历应用:http://oj.leetcode.com/problems/recover-binary-search-tree/
遍历应用:http://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
level遍历:http://oj.leetcode.com/problems/binary-tree-level-order-traversal/
level 遍历:http://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
level 遍历变种:http://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
level 遍历变种:http://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

上一篇:old problems


下一篇:eclipse 项目没错却有红叉(解决方法)